Algorithm | Binary Search

花了半天把二分查找的几种都写了一遍。验证了一下。二分查找的正确编写的关键就是，确保循环的初始、循环不变式能够保证一致。

可以先从循环里面确定循环不变式，然后再推导初始条件，最后根据循环不变式的内容推导出结果。

1. 普通的二分查找

第一版本：

 1 //first version
 2 int find(int arr[], int n, int target) {
 3     int l = 0, r = n - 1;
 4     while (l <= r) {
 5         int m = l + (r - l) / 2;
 6         if (arr[m] == target) return m;
 7         else if (arr[m] < target) {
 8             l = m + 1;
 9         } else {
10             r = m - 1;
11         }
12     }
13     return -1;
14 }

循环内部有三次比较，一般来说，相等的操作只需要判断一次，所以最好是放在循环最外面判断。

注意这里因为提到外面判断相等的情况了，那么循环退出条件就可以改为l <r，在循环中不需要判断l == r的情形。

 1 //second version
 2 int findLeft(int arr[], int n, int target) {
 3     int l = 0, r = n - 1;
 4     
 5     // [l, r]
 6     while (l < r) {
 7         int m = l + (r - l) / 2; // l < r => m < r
 8         if (arr[m] < target) {
 9             l = m + 1; // l <= m => l need to be added by one ensuring l is always increasing; and arr[l] <= target
10         } else {
11             r = m; // target <= arr[m], [l, r], m < r => if arr[m] == target, we still decrease r, so what we found is the lower_bound
12         }
13     }
14 
15     // [l, r] && r >= l => if (arr[l] == target) => return l;
16     if (l < n && arr[l] == target) return l;
17     else return -1;
18 }

2. 查找最左边的值

同上面的version 2.

关键就是，处理相等的情况。由于是要求最左的位置，所以遇到相等时候，仍要把区间往左移。所以这里是用了r=m。（因为m恒小于r）。

3. 查找最右边的值

这里的关键同样是处理相等的情况。要求的是最右的位置，那么遇到相等的时候，还是要把区间右移，所以这里是l=m+1。之所以要加1，就是因为l<=m的，为了确保循环一定能够退出，要加1，才能确保每次循环，区间都在缩小。但是加了1之后，变成了target==arr[m]的时候，l=m+1, 也就是target > arr[l]。所以最终的结果就是l-1。从这里再去推导初始化的时候，l和r的取值。因为区间是[l-1,r)，所以l=1，r=n。

 1 int findRight(int arr[], int n, int target) {
 2     int l = 1, r = n;
 3 
 4     // [l - 1, r)
 5     while (l < r) {
 6         int m = l + (r - l) / 2;
 7         if (arr[m] > target) { // ensuring target < arr[r] && target > arr[l], [l - 1, r)
 8             r = m; // l < r => m < r, [l - 1, r)
 9         } else {
10             l = m + 1; // l <= m, when target == arr[m], l is still increasing, [l - 1, r), target >= arr[l - 1] = arr[m]
11         }
12     }
13 
14     // [l-1, r)
15     if (l - 1 >= 0 && arr[l - 1] == target) return l - 1;
16     else return -1;
17 }

4. 查找倒数第一个比它小的数；

 1 int findLastSmall(int arr[], int n, int target) {
 2     int l = 0, r = n - 1;
 3     // [l, r]
 4     while (l < r) {
 5         int m = l + (r - l) / 2;
 6         if (arr[m] >= target) {
 7             r = m; // target <= arr[r]
 8         } else {
 9             l = m + 1; // target > arr[m] => target >= arr[m+1], [l, r] 
10         }
11     }
12 
13     // target is in [l, r], so the last smaller number is r
14     if (target > arr[l]) return l;
15     return l - 1;
16 }

因为循环中确保了target >= arr[l] && target <= arr[r]，那么我们要判断target[l]是否等于target，如果等于，返回的是l-1。否则返回的就是l。

5. 查找第一个比它大的数；

int findFirstLarge(int arr[], int n, int target) {
    int l = 1, r = n;
    // [l - 1, r)
    while (l < r) {
        int m = l + (r - l) / 2;
        if (arr[m] <= target) { // target >= arr[l - 1]
            l = m + 1; // l is increasing, [l - 1, r)
        } else { // target < arr[m]
            r = m; // target < arr[r],[l - 1, r) 
        }
    }
    // target is in [l - 1, r), so the first larger number is r
    return r;
}

这个比较简单，因为循环确定target>=arr[l]&&target < arr[r]，那么第一个比target大的数肯定就是arr[r]。

Worst case performance: O(log n)
Best case performance: O(1)
Average case performance: O(log n)
Worst case space complexity: O(1)

今天算是把怎么验证程序的正确性研究了一天了。。。20140923