Implement binary search in Javascript:
/* Returns either the index of the location in the array,
or -1 if the array did not contain the targetValue */
var doSearch = function(array, targetValue) {
var min = 0;
var max = array.length - 1;
var guess;
var i = 1;
while(min <= max) {
guess = Math.floor((max + min) / 2);
if (array[guess] === targetValue) {
println("Total guesses " +i);
return guess;
}
else if (array[guess] < targetValue) {
min = guess + 1;
}
else {
max = guess - 1;
}
i = i+1;
println(guess);
}
return -1;
};
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
var result = doSearch(primes, 73);
println("Found prime at index " + result);
Program.assertEqual(doSearch(primes, 73), 20);
Program.assertEqual(doSearch(primes, 97), 24);
Program.assertEqual(doSearch(primes, 11), 4);
We use big-Θ notation to asymptotically bound the growth of a running time to within constant factors above and below.
We use big-O notation for asymptotic upper bounds, since it bounds the growth of the running time from above for large enough input sizes. It basically means "the running time grows at most this much, but it could grow more slowly."
We can say that the running time of binary search is always O(lgn). We can make a stronger statement about the worst-case running time: it's Θ(lgn).
We use big-Ω notation to say that an algorithm takes at least a certain amount of time, without providing an upper bound. So the running time is "big-Ω of f(n)." We use big-Ω notation for asymptotic lower bounds, since it bounds the growth of the running time from below for large enough input sizes.
IMPORTANT: We can say that binary search always runs in O(lgn) time but not that it always runs in Θ(lgn) time. Θ(f(n)) automatically implies O(f(n)) AND Ω(f(n)).
Here is a list of functions in asymptotic notation that we often encounter when analyzing algorithms, listed from slowest to fastest growing.
- Θ(1)
- Θ(lgn)
- Θ(n)
- Θ(nlgn)
- Θ(n2)
- Θ(n2lgn)
- Θ(n3)
- Θ(2n)
- A function has "constant" growth if its output does not change based on the input, the . The easy way to identify constant functions is find those that have no in their expression anywhere, or have --> 1 and 1000 are constant.
- A function has "linear" growth if its output increases linearly with the size of its input. The way to identify linear functions is find those where is never raised to a power (although is OK) or used as a power. --> 3n and (3/2)n are linear.
- A function has "polynomial" growth if its output increases according to a polynomial expression. --> and are polynomial.
- A function has "exponential" growth if its output increases according to an exponential expression. The way to identify exponential functions is to find those where a constant is raised to some expression involving . --> and are exponential.
var indexOfMinimum = function(array, startIndex) {
// Set initial values for minValue and minIndex,
// based on the leftmost entry in the subarray:
var minValue = array[startIndex];
var minIndex = startIndex;
// Loop over items starting with startIndex,
// updating minValue and minIndex as needed:
for (var i = minIndex+1; i<array.length;i++){
if(array[i]<array[minIndex]){
minIndex = i;
minValue=array[i];} }
return minIndex;
};
var array = [18, 6, 66, 44, 9, 22, 14];
var index = indexOfMinimum(array, 2);
// For the test array [18, 6, 66, 44, 9, 22, 14],
// the value 9 is the smallest of [..66, 44, 9, 22, 14]
// Since 9 is at index 4 in the original array,
// "index" has value 4
println("The index of the minimum value of the subarray starting at index 2 is " + index + "." );
Program.assertEqual(index, 4);
Program.assertEqual(indexOfMinimum(array, 5), 6);
Program.assertEqual(indexOfMinimum(array, 3), 4);
Implement selection sort:
var selectionSort = function(array) {
var minIndex;
for (var i = 0; i < array.length; i++) {
minIndex = indexOfMinimum(array, i);
swap(array, i, minIndex);
}
};
var array = [22, 11, 99, 88, 9, 7, 42];
selectionSort(array);
println("Array after sorting: " + array);
Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);
array = [22, 11, 99, 88, 9, 7, 42,1];
selectionSort(array);
Program.assertEqual(array, [1, 7, 9, 11, 22, 42, 88, 99]);
array = [22, 11, 0, 88, 9, 7, 42,1];
selectionSort(array);
Program.assertEqual(array, [0, 1, 7, 9, 11, 22, 42, 88]);
Computing summations from 1 to n:
A faster way to calculate 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 is:
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9
=4⋅9=36 .
Add the smallest and the largest number and then multiply by the number of pairs.
What if the sequence to sum up goes from 1 to ? We call this an arithmetic series. The sum of the smallest and largest numbers is . Because there are n numbers altogether, there are pairs (whether n is odd or even). Therefore, the sum of numbers from 1 to is , which equals .
- Call
insert
to insert the element that starts at index 1 into the sorted subarray in index 0. - Call
insert
to insert the element that starts at index 2 into the sorted subarray in indices 0 through 1. - Call
insert
to insert the element that starts at index 3 into the sorted subarray in indices 0 through 2. - …
- Finally, call
insert
to insert the element that starts at index n−1 into the sorted subarray in indices 0 through n−2.
Implement insert sort (running time Θ(n2)):
var insert = function(array, rightIndex, value) {
var i;
for (i = rightIndex; i >= 0 && array[i] > value; i--) {
array[i + 1] = array[i];
}
array[i + 1] = value;
};
var insertionSort = function(array) {
for (var i = 1; i < array.length; i++) {
insert(array, i - 1, array[i]);
}
};
var array = [3, 5, 7, 11, 13, 2, 9, 6];
insert(array, 4, 2);
println("Array after inserting 2: " + array);
Program.assertEqual(array, [2, 3, 5, 7, 11, 13, 9, 6]);
Difference between Insertion and Selection sort:
- Insertion sort: inserts the next element at the correct position;
- Selection sort: selects the smallest element and exchange it with the current item;
The running times for insertion sort:
- Worst case: .
- Best case: . <--almost sorted array
- Average case for a random array: .
- "Almost sorted" case: .