Binary Search

Problem

http://www.lintcode.com/en/problem/binary-search/

For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

Example

If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

Notes

是对有序数组进行搜索，4 key steps：

1. start + 1 < end
2. start + (end - start) / 2
3. A[mid] ==, <, >
4. A[start] A[end] ? target

二分查找不能应用于输入为空的情况，或者说需要单独排除这种corner case

Solution

//four steps in a clissic binary search method!!
class Solution {
public:
    /**
     * @param nums: The integer array.
     * @param target: Target number to find.
     * @return: The first position of target. Position starts from 0. 
     */
    int binarySearch(vector<int> &array, int target) {
        // write your code here
        if(array.size() == 0)
            return -1;
        int start = 0;
        int end = array.size() - 1;
        int mid;
        while(start+1 < end) {//1.
            mid = start + (end-start)/2; //step 2
            if(array[mid] == target) { //step 3
                end = mid;
               // break; //CANNOT BREAK HERE! find the FIRST index
            } else if(array[mid] > target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if(array[start] == target) //step 4
            return start;
        if(array[end] ==  target)
            return end;
        return -1;
    }
};

//solution 2: recursive method
class Solution {
public:
    /**
     * @param nums: The integer array.
     * @param target: Target number to find.
     * @return: The first position of target. Position starts from 0. 
     */
    int binarySearch(vector<int> &array, int target) {
        // write your code here
        if(array.size() == 0)
            return -1;
        int start = 0;
        int end = array.size() - 1;
        recursion_bs(array, target, start, end);
        if(array[start] == target) //step 4
            return start;
        if(array[end] ==  target)
            return end;
        return -1;
    }
private: 
    void recursion_bs(vector<int> &array, int target, int &start, int &end) {
        if(start+1 >= end) //step 1
            return;
        int mid = start + (end-start)/2;
        if(array[mid] ==  target){
            end = mid;
        }
            //return mid;
        else if(array[mid] > target){
            end = mid;
            //return recursion_bs(array, target, start, mid-1);
        }
        else{
            start = mid;
            //return recursion_bs(array, target, mid+1, end);
        }
        recursion_bs(array, target, start, end);
    }
};

通过比较start和end可以确定最终seardh的结果了。