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
.