Divide & conquer 2: binary search

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return bin_search(nums, 0, nums.size() - 1, target);
    }
    int bin_search(vector<int>& nums, int l, int h, int target){
        if(l > h) return -1;
        int mid = (l + h)  / 2;
        if(nums[mid] == target) return mid;
        if(nums[mid] > target){
            // target in [l: mid - 1]
            return bin_search(nums, l, mid - 1, target);
        }
        return bin_search(nums, mid + 1, h, target);

    }
};

One thing that helps with this recursive problem is to set the boundary of input for the algorithm.
For binary search, a bin_search(nums, int l, int h, int target), specify that this will search [l, h] for target. So for the subproblems, you will know that it will search between [l, mid – 1] and [mid + 1, h] with bin_search.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax