二分查找

时间复杂度O(logn)

二分查找必须先要给序列排序，也就是说要使用二分查找算法，序列必须是有序的。

1.普通的二分查找  LeetCode 704. 二分查找

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

递归的写法：

class Solution { public: int _search(vector<int>& nums, int left, int right, int target) { if(left > right) return -1; int mid = ((right - left) >> 1) + left;//"+"比">>"优先级高 if(nums[mid] == target) return mid; else if(nums[mid] > target) return _search(nums, left, mid-1, target); else return _search(nums, mid+1, right, target); } int search(vector<int>& nums, int target) { return _search(nums, 0, nums.size()-1, target); } };

注意：int mid = (l + r) / 2;可以优化为：int mid = (r - l) / 2 + l;//防止l+r越界。除以2也可优化为按位右移：int mid =（(r - l) / >>1） + l

2.二分查找的变种问题：找第一个目标元素或者找最后一个目标元素，比如：1，2，3，3，4，5 target=3，第一个3就是返回下标2，最后一个就是返回下标3.

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

class Solution { public: int searchLeft(vector<int>& nums, int target) { int l = 0, r = nums.size()-1; while(l <= r) { int mid = ((r - l) >> 1) + l; if(nums[mid] > target) r = mid - 1; else if(nums[mid] < target) l = mid + 1; else{ if(mid == 0 || nums[mid-1] != target) return mid;//注意mid与可能到第一个元素，那么nums[mid+1]就会数组越界 else r = mid - 1; } } return -1; } int searchRight(vector<int>& nums, int target) { int l = 0, r = nums.size()-1; while(l <= r) { int mid = ((r - l) >> 1) + l; if(nums[mid] > target) r = mid - 1; else if(nums[mid] < target) l = mid + 1; else{ if(mid == nums.size()-1 || nums[mid+1] != target) return mid;//注意mid与可能到最后一个元素，那么nums[mid+1]就会数组越界 else l = mid + 1; } } return -1; } vector<int> searchRange(vector<int>& nums, int target) { vector<int> res; int left = searchLeft(nums, target); int right = searchRight(nums, target); res.push_back(left); res.push_back(right); return res; } };

3.求x的平方根 LeetCode 69. x 的平方根

class Solution { public: int mySqrt(int x) { if(x <= 1 ) return x; int left = 0, right = x, ret; while(left <= right) { int mid = (right - left) / 2 + left; int target = x / mid; if(mid == target )//target = x / mid;此题可转换为查找最后一个不大于目标值的元素 return mid; else if( target < mid)//目标值小于选定值，所以区间要向左边收缩 { right = mid - 1; } else { left = mid + 1; ret = mid;//比如6,当mid=2时，真正的结果在2-3之间，但结果取2 } } return ret; } };

4.二分查找变种：

（1）查找第一个大于等于目标元素（1，2，4，6 target=3,结果返回4）；

int search(vector<int>& nums, int target) { int l = 0, r = nums.size()-1; while(l <= r) { int mid = ((r - l) >> 1) + l; if(nums[mid] >= target) { if(mid == 0 || nums[mid-1] <target) return mid; else r = mid - 1; } else l = mid + 1; } return -1; }

（2）查找最后一个小于给定元素（1，2，4，6 target=3,结果返回2。

int search(vector<int>& nums, int target) { int l = 0, r = nums.size()-1; while(l <= r) { int mid = ((r - l) >> 1) + l; if(nums[mid] <= target) { if(mid == 0 || nums[mid+1] > target) return mid; else l = mid + 1; } else r = mid - 1; } return -1; }