二分查找相关题目

二分法模板： https://www.acwing.com/blog/content/31/

有序数组中查找

1. LeetCode 34. Find First and Last Position of Element in Sorted Array

 1 class Solution {
 2 public:
 3     vector<int> searchRange(vector<int>& nums, int target) {
 4         vector<int> ans = {-1, -1};
 5         if(nums.size() == 0) return ans;
 6         int l=0, r=nums.size();
 7         // 找到最左边的元素
 8         while(l < r){
 9             int mid = l + (r - l) /2;
10             if(nums[mid] >= target)
11                 r = mid;
12             else
13                 l = mid + 1;
14         }
15         if(l==nums.size() || nums[l] != target)
16             return ans;
17     
18         ans[0] = l;
19         // 找最右边的元素
20         r = nums.size();
21         while(l < r){
22             int mid = l + (r - l) /2;
23             if(nums[mid] > target)
24                 r = mid;
25             else
26                  l = mid+1;
27             // 错误写法
28             //if(nums[mid] > target) r = mid - 1;
29             //else l = mid;     // 当l==mid, r保持不变时会死循环，
30         }
31         ans[1] = l-1;
32         return ans;
33     }
34 };

有序数组的旋转

2. Leetcode 33. Search in Rotated Sorted Array https://leetcode.com/problems/search-in-rotated-sorted-array/

 1 class Solution {
 2 public:
 3     int search(vector<int>& nums, int target) {
 4         if(nums.empty()) return -1;
 5         int l=0, h=nums.size()-1;
 6         while(l < h){
 7             int mid = l + (h - l) / 2;
 8             // mid在旋转数组的尾端
 9             if(nums[mid] < nums[h])
10                 if(target > nums[mid] && target <= nums[h])
11                     l= mid + 1;
12                 else
13                     h = mid;
14             // mid在旋转数组的头端
15             else
16                 if(target >= nums[l] && target <= nums[mid])
17                     h = mid;
18                 else
19                     l = mid + 1;
20         }
21         return nums[l]==target ? l : -1;
22     }
23 };

无序数组也可以用二分搜索, 查找局部最大/最小值

3. LeetCode 162. Find Peak Element https://leetcode.com/problems/find-peak-element/

 1 class Solution {
 2 public:
 3     int findPeakElement(vector<int>& nums) {
 4         if(nums.empty()) return -1;
 5         int l=0, h=nums.size()-1;
 6         while(l < h){
 7             int mid = l + (h - l) / 2;
 8             if(nums[mid] < nums[mid+1])
 9                 l = mid + 1;
10             // 此时nums[mid]>nums[mid+1], 若nums[mid]>nums[mid-1],则nums[mid]
11             // 就是峰值，否则nums[mid]<nums[mid-1],表明峰值在左半区间。画图看一下就明白了
12             else
13                 h = mid;
14         }
15         return l;
16     }
17 };

4. LeetCode 287. Find the Duplicate Number https://leetcode.com/problems/find-the-duplicate-number/

 1 class Solution {
 2 public:
 3     int findDuplicate(vector<int>& nums) {
 4         int l=1, n=nums.size(), h=n-1;
 5         // l,h不是索引，是数的取值范围
 6         while(l < h){
 7             int mid = l + (h - l) / 2;   // 中间大小的数
 8             int cnt=0;                   // 计算比mid小的数有几个
 9             for(int i=0; i<n; ++i)
10                 if(nums[i] <= mid)
11                     ++cnt;
12             // 比mid小的数个数比mid大，表明1~mid中间有重复的数字
13             if(cnt > mid)    
14                 h = mid;
15             else
16                 l = mid + 1;
17         }
18         return l;
19     }
20 };