Guest User

Untitled

a guest
Apr 19th, 2010
392
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. /**
  5.  * Search for value x in given array of N elements
  6.  *
  7.  * Return the index at which the element can be found,
  8.  * or -1 if the element was not found.
  9.  */
  10. int binary_search(int x, int* array, int N) {
  11.     if (N == 0) return -1;
  12.  
  13.     // Search space is [lo..hi)
  14.     int lo = 0, hi = N;
  15.     while (lo + 1 < hi) {
  16.         int h = (hi + lo) / 2;
  17.         if (array[h] <= x) lo = h;
  18.         if (array[h] > x)  hi = h;
  19.     }
  20.  
  21.     return array[lo] == x ? lo : -1;
  22. }
  23.  
  24. // [3..5)
  25. // h = 4
  26.  
  27. int main() {
  28.     int N = 8;
  29.     int array[] = { 1, 3, 4, 4, 7, 10, 13, 20 };
  30.  
  31.     printf("15: %d\n",  binary_search(15, array, N));
  32.     printf("4: %d\n",   binary_search(4,  array, N));
  33.     printf("1: %d\n",   binary_search(1,  array, N));
  34.     printf("20: %d\n",  binary_search(20, array, N));
  35.  
  36.     return 0;
  37. }
RAW Paste Data