二分法总结

二分查找本身并不难, 难的是二分查找的扩展问题

1. 假如 target 不在数组中, 输入其应该在的位置

2. 找到大于 target 的最小值的位置或小于 target 的最大值的位置

3. target 在数组中连续出现多次, 分别找到 target 的最左位置和最右位置

int _bsearch(int A[], int m, int n, int target) {

　　if(m > n)                                              ----------------------------- 变量 x

　　　　return m;                                       ----------------------------- 变量 y

　　int mid = (m+n) >> 1;                   

　　if(A[mid] == target) {        

　　　code here　                                       ----------------------------- 变量 z

　　}

}

在二分查找的框架内, 大致有 3 个可变的位置, 分别是 x, y, z 处

具体来说

1. x 可以填写 m >=n 或 m > n

2. y 可以填写 return m, return n, return min(n,m)...

3. z 可以填写 b_search(A, mid+1, n, target) or b_search(A, m, mid-1, target)

一般来讲, 

x 处都要填 m > n, 因为当 m==n 时, 代码还需要向下走进行验证

y 处是最难把握的了, 需要具体情况具体分析

z 的话需要考虑 当 a[mid] == target 时, 我们有怎样的需求, 再做选择

例题

1. Leetcode Search in Rotated Sorted Array

class Solution {
public:
    int search(int A[], int n, int target) {
    	if(n < 1)
    		return -1;

		int pivot = A[0];        
		int pivot_pos = find_pos(A, 0, n-1, pivot);

		//cout << "pivot at " << pivot_pos << endl;

		int got;
		if(pivot == target) {
			return 0;
		}else if(pivot < target) {
			got = b_search(A, 0, pivot_pos-1, target);
			if(got < 0 || got >= pivot_pos)
				return -1;
			return got;
		}else{
			got = b_search(A, pivot_pos, n-1, target);
			if(got < pivot_pos || got >= n)
				return -1;
			return got;
		}


    }

    int find_pos(int A[], int m, int n, int pivot) {
    	if(m > n)
    		return m;

    	int mid = (m+n)>>1;
    	//cout << "mid " << mid << endl;
    	if(A[mid] >= pivot) {
    		return find_pos(A, mid+1, n, pivot);
    	}else {
    		return find_pos(A, m, mid-1, pivot);
    	}
    }

    int b_search(int A[], int m, int n, int pivot) {
    	if(m > n) {
    		return -1;
    	}

    	int mid = (m+n)>>1;
    	if(A[mid] == pivot) {
    		return mid;
    	}else if(A[mid] < pivot) {
    		return b_search(A, mid+1, n, pivot);
    	}else{
    		return b_search(A, m, mid-1, pivot);
    	}

    }
};

　　

2. Leetcode  Search Insert Position

y 处. 当 m > n 时, 说明有两种情况发生了, 第一, 上一步是 b_search(A, mid+1, n, target) 这说明, 待求位置在 mid "右边"(A[mid] < target), 所以返回 m (mid+1);  第二种, 上一步是 b_search(A, m, mid-1, target), 说明 (A[mid] > target) 且这是最后一步递归(以发生越界 m>n), 所以我们要插入的位置在mid-1右边, 仍然填 m

#include <iostream>
using namespace std;

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int pos = b_search(A, 0, n-1, target);
        return pos;
    }

    int b_search(int A[], int m, int n, int target) {
    	if(m > n)
    		return m;

    	int mid = (m+n)>>1;
    	//cout << mid << endl;
    	if(A[mid] == target) {
    		return mid;
    	}else if(A[mid] > target) {
    		return b_search(A, m, mid-1, target);
    	}else{
    		return b_search(A, mid+1, n, target);
    	}
    }
};

　　

3. Leetcode Search for a Range

x 处. m==n 时, 仍需要判断, 所以向下走

z 处. 求 left_position 时, 当 A[mid] == target 时, 我们希望看看 mid 左边是否还有更合适的解, 所以应该 b_search(A, m, mid-1, target) 强制向左, 求 right_position 同理

y 处. 求 left_position 时, 我们总是强制向左, 所以最终会越界, left_position 应该是越界的右端, 返回 m

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        int left = left_pos(A, 0, n-1, target);
        int right = right_pos(A, 0, n-1, target);
        
        if(left < 0 || left >= n || A[left] != target) {
        	left = right = -1;
        }

        vector<int> res;
        res.push_back(left);
        res.push_back(right);

        return res;
    }
    
    int left_pos(int A[], int m, int n, int target) {
    	if(m > n)
    		return m;

    	int mid = (m+n)>>1;

    	// when a[mid] == target, prefer left one
    	if(A[mid] >= target) {
    		return left_pos(A, m, mid-1, target);
    	}else{
    		return left_pos(A, mid+1, n, target);
    	}
    }

    int right_pos(int A[], int m, int n, int target) {
    	if(m > n)
    		return n;

    	int mid = (m+n)>>1;
    	//cout  << mid << endl;
    	// when a[mid] == target, prefer right one
    	if(A[mid] > target) {
    		return right_pos(A, m, mid-1, target);
    	}else{
    		return right_pos(A, mid+1, n, target);
    	}
    }
};