CC++ 笔试面试（2）——二分查找

 Bentley在他的著作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。

难怪有人说，二分查找原理简单，甚至小学生都能明白。不过这查找算法好多专家都写不好。我自己尝试了一下,确实要第一次就完全写正确不容易.以下两份实现依次为迭代和递归版本的代码,二分查找的思想很多人都清楚,但是这里有一个细节就是要注意边界的选择。

[cpp] view plain copy print ? //迭代方法  int search(int array[], int n, int v)  {      int left, right, middle;        left = 0, right = n - 1;        while (left <= right)      {          middle = (left + right) / 2;          if (array[middle] > v)          {              right = middle - 1;          }          else if (array[middle] < v)          {              left = middle + 1;          }          else          {              return middle;          }      }        return -1;  }  //递归方法  int search_recurse(int array[], int low, int high, int v)  {      int middle;        middle = (low + high) / 2;        if (low < high)      {          if (array[middle] > v)          {              return search_recurse(array, low, middle, v);          }          else if (array[middle] < v)          {              return search_recurse(array, middle + 1, high, v);          }          else          {              return middle;          }      }      else if (low == high)      {          if (array[middle] == v)          {              return middle;          }          else          {              return -1;          }        }      else      {          return -1;      }        return -1;  }    int main()  {      int array[] = {0, 1, 2, 3, 4, 5, 6, 7, 13, 19};        int m = search(array, sizeof(array)/sizeof(array[0]), 13);        printf("m = %d\n", m);        m = search_recurse(array, 0, sizeof(array)/sizeof(array[0]), 13);        printf("m = %d\n", m);        return 0;  }