プログラミング言語 C 3.1

本に掲載されている二分探索よりも条件分岐が少ないものを書けという
問題。なんか返ってややこしくなる感じがあるので、普通に教科書に書いて
いる方を使った方が良さげな気はしますね。

#include <stdio.h>
#include <assert.h>

static int binary_search(int x, int *a, int n);
static int test_binary_search();

int
main(void)
{
     test_binary_search();
}

static int
test_binary_search()
{
     int a[] = {0, 1, 2, 3, 4, 5, 6, 7 ,8 ,9};

     assert(binary_search(-10, a, 10) == -1);
     assert(binary_search(10, a, 10) == -1);
     assert(binary_search(0, a, 10) == 0);
     assert(binary_search(9, a, 10) == 9);
     assert(binary_search(5, a, 10) == 5);
}

static int
binary_search(int x, int *a, int n)
{
     int low, high, mid;

     low  = 0;
     high = n - 1;

     mid = (low + high) / 2;
     while (low <= high && x != a[mid]) {
          if (x > a[mid]) {
               low = mid + 1;
          }
          else {
               high = mid - 1;
          }
          mid = (low + high) / 2;
     }

     if (x == a[mid]) {
          return mid;
     }

     return -1;
}