(New page: 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 betwe...)
 
Line 1: Line 1:
Binary Search
+
= Binary Search =
  
Cuts the search area in half every time until the number is found
+
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)
+
(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
+
For Example: Search for a number between 0 and 100. Search for : 63  
  
| ||||||||||||||||||||||<br>O 50 100<br>(first search eliminates anything less than 50)
+
|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ||||||||||||||||||||||<br>0&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 50&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 100<br>(first search eliminates anything less than 50)  
  
||||||||||||||||||||| |<br>50 75 100<br>(second search eliminates anything greater than 75)
+
||||||||||||||| &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; |<br>50&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 75&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 100<br>(second search eliminates anything greater than 75)  
  
| |||||||||||||||||||||<br>50 63 75<br>(at this point, the algorithm sees that 63 is one of the boundaries and the number has been found)
+
|&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; |||||||||||||||||||||<br>50&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 63&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 75<br>(at this point, the algorithm sees that 63 is one of the boundaries and the number has been found)  
  
Code for a Binary Search:<br>int binary_search(int *v,int value, int min_ndx,int max_ndx){<br> <br> int mid_ndx = (max_ndx + min_ndx)/2;<br> <br> //Base Step 1 - Ensures that the minimum index is larger than the maximum index<br> if (min_ndx &gt; max_ndx){<br> return -1;<br> }<br> <br> //Baser Step 2 - Checks to see if the Middle Value is the Value that is being searched for<br> if(v[mid_ndx] == value){<br> return mid_ndx;<br> }<br> <br> //Recursive Steps<br> <br> if (value &lt; v[mid_ndx]){<br> return binary_search(v, value, min_ndx, mid_ndx - 1);<br> }<br> else {<br> return binary_search(v, value, mid_ndx + 1, max_ndx);<br> }<br>}
+
Example Code for a Binary Search:
  
Selection Sort
+
<br>int binary_search(int *v,int value, int min_ndx,int max_ndx){<br> &nbsp;&nbsp;&nbsp; int mid_ndx = (max_ndx + min_ndx)/2;<br> <br>&nbsp;&nbsp;&nbsp; //Base Step 1 - Ensures that the minimum index is larger than the maximum index<br>&nbsp;&nbsp;&nbsp; if (min_ndx &gt; max_ndx){<br>&nbsp;&nbsp;&nbsp; return -1;<br>&nbsp;&nbsp;&nbsp; }<br> <br>&nbsp;&nbsp;&nbsp; //Baser Step 2 - Checks to see if the Middle Value is the Value that is being searched for<br>&nbsp;&nbsp;&nbsp; if(v[mid_ndx] == value){<br>&nbsp;&nbsp;&nbsp; return mid_ndx;<br>&nbsp;&nbsp;&nbsp; }<br> <br>&nbsp;&nbsp;&nbsp; //Recursive Steps<br> <br>&nbsp;&nbsp;&nbsp; if (value &lt; v[mid_ndx]){<br>&nbsp;&nbsp;&nbsp; return binary_search(v, value, min_ndx, mid_ndx - 1);<br>&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; else {<br>&nbsp;&nbsp;&nbsp; return binary_search(v, value, mid_ndx + 1, max_ndx);<br>&nbsp;&nbsp;&nbsp; }<br>}
  
Example: Sort the following list of numbers 14,4,92,74,3
+
= Selection Sort =
  
(N.B. - the bolded numbers are the ones that the algorithm is searching through)
+
Example: Sort the following list of numbers 14,4,92,74,3
  
14 4 92 74 3<br>(First iteration - looks for the smallest number out of the entire set – “3” - and switches its location with the first element in the list)
+
(N.B. - the bolded numbers are the ones that the algorithm is searching through)  
  
3 4 92 74 14<br>(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 )
+
'''14 4 92 74 3'''<br>(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<br>(Third Iteration – finds “14” as the smallest number swaps it with the number in the third position on the list)
+
3 '''4 92 74 14'''<br>(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 14 74 92<br>(Fourth iteration – finds “74” as the smallest number and swaps it with the fourth number in the list.)
+
3 4 '''92 74 14'''<br>(Third Iteration – finds “14” as the smallest number swaps it with the number in the third position on 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.
+
3 4 14 '''74 92'''<br>(Fourth iteration – finds “74” as the smallest number and swaps it with the fourth number in the list.)
  
Code for a Selection Sort:<br>void selection_sort(int *v,int items){<br> int i,j;<br> for (i = 0;i &lt; items -1;i++){<br> int min_ndx;<br> int min_value = v[i];<br> <br> for (j = i;j &lt; items;j++){<br> if (v[j] &lt; min_value){<br> min_value = v[j];<br> min_ndx = j;<br> }<br> }<br> v[min_value] = v[i];<br> v[i] = min_value;<br> }<br>} <br>
+
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:<br>void selection_sort(int *v,int items){<br>&nbsp;&nbsp;&nbsp; int i,j;<br>&nbsp;&nbsp;&nbsp; for (i = 0;i &lt; items -1;i++){<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int min_ndx;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int min_value = v[i];<br> <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (j = i;j &lt; items;j++){<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (v[j] &lt; min_value){<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; min_value = v[j];<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; min_ndx = j;<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; v[min_value] = v[i];<br>&nbsp;&nbsp;&nbsp; v[i] = min_value;<br>&nbsp;&nbsp;&nbsp; }<br>} <br>

Revision as of 15:39, 27 April 2011

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

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett