Revision as of 15:36, 27 April 2011 by Ncapriol (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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;
}
}

Alumni Liaison

Abstract algebra continues the conceptual developments of linear algebra, on an even grander scale.

Dr. Paul Garrett