建议使用左闭右开区间[l, r)查找。二分查找的最后，索引l，r会落到右区间第一个元素位置。因此但凡是能够见数组分成左右两个区间的都能应用二分查找法。

1、普通查值

常见问题方式：寻找含重复值的有序数组 `[...,a, tar, tar, tar,.b....]`，找到tar元素的上下边界位置。

（1）寻找下边界：

俗称lower_bound，将[...a]看做左区间，[tar,tar,tar,b...]看做右区间，因此左区间向右移动的条件是，否则右区间向左移动；（如果找不到，右区间第一个大于tar的元素）。

int lower_bound(int[] nums, int n, int tar)
{int left = 0, right = n;while(left < right){int mid = left + (right-left)/2;if(nums[mid]<tar) left = mid+1;else right = mid;}return left;//查找结束后，不管找没找到目标值，right==left，返回哪个都行。
}

（2）寻找上边界

俗称upper_bound，将[...a,tar,tar,tar]看做左区间，[b...]看做右区间，upper bound是l-1。因此左区间向右移动的条件是，否则右区间向左移动；（如果找不到，右区间第一个大于tar的元素）。

2、旋转数组查找

含义：对于[1 2 3 4 5]向右旋转两次为[4 5 1 2 3]称为旋转数组。

（1）无重复元素时 查找指定元素位置

33. 搜索旋转排序数组

思路：对于[1 2 3 4 5]，[4 5 1 2 3]两种旋转数组类型，可以根据target与nums[0]大小关系分成左右两区间。当target在左区间(tar>-nums[0])时，nums[mid]在右区间或在左区间但大于target都要向左移动，只有nums[mid]在左区间且小于taget向右移动。当taget在右区间同理分析。

平均时间复杂度O(logn)，最坏时间复杂度O(n)

    int search(vector<int>& nums, int target) {if (nums.empty()) return -1;if (target == nums[0]) return 0;int n = nums.size(), l = 0, r = n;while (l < r) {int mid = (l+r)/2;if (nums[mid] == target) {return mid;}if (target >= nums[0]) {//target在左区间//当前值在左区间且当前值小于目标值往右走if (nums[mid] >= nums[0] && nums[mid] < target)l = mid +1;else//其他情况都往左走 r = mid;}else {//当前值在右区间且当前值大于目标值往左走if (nums[mid] <= nums[0] && nums[mid] > target) r = mid;elsel = mid +1;}}return -1;}

（2）含重复元素时 查找元素位置

81. 搜索旋转排序数组2

旋转数组含有重复元素，且重复元素在数组首尾时，就无法根据taget与nums[0]关系分成左右区间了，我们可以左右收缩派出重复元素，再根据上一题思路进行查找。

    bool search(vector<int>& nums, int target) {int n = nums.size(), l=0, r=n-1;if (target == nums[0]) return true;//因为要跳过首尾重复元素，先判断下while (l+1 <n && nums[l] == nums[l+1]) ++l;while (r-1>=0 && nums[r] == nums[r-1]) r--;if (l >= r) return false;//全部重复if (nums[l] == nums[r]) --r;//上面收缩后仍有可能左右边界元素相同++r;//右边界取不到int begin = nums[l];while (l < r) {int mid = (l+r)/2;if (target == nums[mid]) {return true;}if (target >= begin) {if (nums[mid] >= begin && nums[mid] < target) l = mid+1;else r = mid;}else {if (nums[mid] < begin && nums[mid] > target) r = mid;else l = mid+1;}}return false;}

（3）无重复值 寻找最小值

153. 寻找旋转排序数组中的最小值

二分法是数组按某种规律分成两个区间就可以用，最终索引落到右区间第一个元素。

该题两种情况：3 4 5 1 2       [3 4 5]向右 [1 2]向左

                1 2 3 4 5       [1 2 3 4 5]向左

所以规律是nums[mid] < nums.back向左，但是和nums[0]比较不是很符合

    int findMin(vector<int>& nums) {int n = nums.size(), l = 0, r = n;while (l < r) {int mid = (l+r)/2;if (nums[mid] > nums.back()) l = mid+1;else r = mid;}return nums[l];}

（4）有重复值 寻找最小值

154. 寻找旋转排序数组中的最小值 II

同理向去处左右重复值.平均时间复杂度O(logn)，最坏时间复杂度O(n)

    int findMin(vector<int>& nums) {int n = nums.size(), l =0, r = n-1;while (l<n-1 && nums[l] == nums[l+1]) ++l;while (r >=1 && nums[r] == nums[r-1])--r;if (l >= r) return nums[0];if (nums[l] == nums[r]) --r;++r;int end = r;while (l < r) {int mid = (l+r)/2;if (nums[mid] > nums[end-1]) l = mid+1;else r = mid;}return nums[l];}

（5）寻找峰值元素

对于单峰值数组。有三种情况，峰值在中间，递增数组、递减数组。根据趋势将数组分为左右区间

    int findPeakElement(vector<int>& nums) {int n = nums.size(), l = 0, r=n;while (l < r) {int mid = (l+r)/2;//把n-1放到右区间，如果数组一直递增，那么l最终落到n-1上符合题目if (mid+1<n && nums[mid] < nums[mid+1]) l = mid + 1;else r = mid;}return l;}

土地资源文秘网