Latest revision as of 06:24, 11 July 2012

ECE264: 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

0-----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)

Example 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 made)

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

Back to ECE264, Spring 2011, Prof. Lu