diff options
| author | Kyle K <kylek389@gmail.com> | 2010-11-25 02:05:16 -0600 |
|---|---|---|
| committer | Kamil Kaminski <kamilkss@gmail.com> | 2010-11-25 02:05:16 -0600 |
| commit | 5f01c5be65e94954e57a0798263807f699f3173f (patch) | |
| tree | ae678ee5b17a6e86b70daba203a9d7e977af023b /sorts.c | |
| parent | bf301724bcda4f53bfe315c19b09951e59bed7e4 (diff) | |
| download | sorts-5f01c5be65e94954e57a0798263807f699f3173f.tar.gz sorts-5f01c5be65e94954e57a0798263807f699f3173f.tar.bz2 sorts-5f01c5be65e94954e57a0798263807f699f3173f.zip | |
implement binary search
Diffstat (limited to 'sorts.c')
| -rw-r--r-- | sorts.c | 19 |
1 files changed, 19 insertions, 0 deletions
@@ -29,7 +29,26 @@ int *mk_rand_arr(int, int); void mergesort(int *, int, int); void merge(int *, int, int, int); void shell_sort(int *, int); +int binary_search(int *, int, int, int); +int binary_search(int *a, int low, int high, int target) +{ + while (low <= high) + { + int middle = low + (high - low) / 2; + + if (target < a[middle]) + high = middle - 1; + else if (target > a[middle]) + low = middle + 1; + else + return middle; + } + + return -1; +} + +/* pg 62, k&r 2nd ANSI, running T(N) = O(N^3/2) */ void shell_sort(int *v, int n) { int gap, i, j, temp; |