Binary Search
Cuts the search area in half every time until the number is found
(caveat – the list must be sorted for the binary search to work)
For Example: Search for a number between 0 and 100. Search for : 63
| ||||||||||||||||||||||
O 50 100
(first search eliminates anything less than 50)
||||||||||||||||||||| |
50 75 100
(second search eliminates anything greater than 75)
| |||||||||||||||||||||
50 63 75
(at this point, the algorithm sees that 63 is one of the boundaries and the number has been found)
Code for a Binary Search:
int binary_search(int *v,int value, int min_ndx,int max_ndx){
int mid_ndx = (max_ndx + min_ndx)/2;
//Base Step 1 - Ensures that the minimum index is larger than the maximum index
if (min_ndx > max_ndx){
return -1;
}
//Baser Step 2 - Checks to see if the Middle Value is the Value that is being searched for
if(v[mid_ndx] == value){
return mid_ndx;
}
//Recursive Steps
if (value < v[mid_ndx]){
return binary_search(v, value, min_ndx, mid_ndx - 1);
}
else {
return binary_search(v, value, mid_ndx + 1, max_ndx);
}
}
Selection Sort
Example: Sort the following list of numbers 14,4,92,74,3
(N.B. - the bolded numbers are the ones that the algorithm is searching through)
14 4 92 74 3
(First iteration - looks for the smallest number out of the entire set – “3” - and switches its location with the first element in the list)
3 4 92 74 14
(Second iteration – finds the smallest number left in the search set – “4” – and switches it’s location with the second element in the list. In this particular example, the four is in its proper location from the initial list, so no changes are )
3 4 92 74 14
(Third Iteration – finds “14” as the smallest number swaps it with the number in the third position on the list)
3 4 14 74 92
(Fourth iteration – finds “74” as the smallest number and swaps it with the fourth number in the list.)
Because there are only 5 elements in this list, the algorithm will only run 4 loops. By definition, the fifth loops would show that the last number is in the correct position.
Code for a Selection Sort:
void selection_sort(int *v,int items){
int i,j;
for (i = 0;i < items -1;i++){
int min_ndx;
int min_value = v[i];
for (j = i;j < items;j++){
if (v[j] < min_value){
min_value = v[j];
min_ndx = j;
}
}
v[min_value] = v[i];
v[i] = min_value;
}
}
