NC105 #二分查找-II#
二分查找-II
http://www.nowcoder.com/practice/4f470d1d3b734f8aaf2afb014185b395
二分搜索模板,然后下标前移。
注意:写成left + (right - left) / 2
而不是(left + right) / 2
可以避免溢出。
class Solution { public: int binary_search(vector<int>& nums, int target) { int len = nums.size(); int left = 0, right = len - 1; while(left <= right) { int middle = left + (right - left) / 2; if(nums[middle] == target) return middle; else if(nums[middle] < target) left = middle + 1; else right = middle - 1; } return -1; } int search(vector<int>& nums, int target) { int index = binary_search(nums, target); if(index == -1) return -1; else { while(index - 1 >= 0 && nums[index - 1] == nums[index]) index--; return index; } } };