From 5f01c5be65e94954e57a0798263807f699f3173f Mon Sep 17 00:00:00 2001 From: Kyle K Date: Thu, 25 Nov 2010 02:05:16 -0600 Subject: implement binary search --- sorts.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/sorts.c b/sorts.c index a03dd68..0207fd0 100644 --- a/sorts.c +++ b/sorts.c @@ -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; -- cgit v1.2.3