1.二分查找

704. 二分查找 - 力扣（LeetCode）

?二分查找算法要確定“二段性”，時間復雜度為O(lonN)。為了防止數據溢出，所以求mid時要用防溢出的方式。

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

樸素二分模版

while(left <= right){int mid = left + (right - left) / 2;//防溢出if(......){left = mid + 1;}else if(......){right = mid - 1;}else{return ......;}}

2.在排序數組中查找元素的第一個和最后一個位置

34. 在排序數組中查找元素的第一個和最后一個位置 - 力扣（LeetCode）

用二分查找解決，要查找一個區間要找去左端點和右端點。

1. 查找區間的左端點

細節處理：

????????1. 循環條件 left < right 而不是left <= right?，因為left == right 的時候就是最終結果，無需判斷。如果判斷了就會死循環（當left和right構成的區間中存在結果，并且 nums[mid] >= t時，此時mid也等于left和right，進行上述操作的時候會導致right = mid一直在原地，所以導致死循環）。

????????2. 求中點的操作

left + （right - left）/ 2 要向下取整，當剩兩個點讓mid的指針指向left。

2.查找區間右端點

與查找區間左端點的方法類似，只是處理條件不同。

1.當nums[mid] <= target 時left == mid。

2.當nums[mid] > target 時right == mid - 1。

循環條件：left < right 和上述原因一致。

求中點的方式 left + (right - left + 1) / 2 要向上取整，當剩兩個點讓mid的指針指向right。

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0)return {-1, -1};int left = 0, right = nums.size() - 1;int begin = 0;while(left < right)//確定區間的左端點{int mid = left + (right - left) / 2;//防溢出寫法if(nums[mid] < target)left = mid + 1;elseright = mid;}//判斷是否有結果if(nums[left] != target)return {-1,-1};elsebegin = left;left = 0, right = nums.size() - 1;while(left < right)//確定區間的右端點{int mid = left + (right - left + 1) / 2;if(nums[mid] <= target)left = mid;else right = mid - 1;}//如果存在左端點，那么右端點也一定存在，所以不用判斷了，直接返回return {begin, right};}
};

總結二分模版

        while(left < right){int mid = left + (right - left) / 2;if(......)left = mid + 1;elseright = mid;}while(left < right)//確定區間的右端點{int mid = left + (right - left + 1) / 2;if(......)left = mid;else right = mid - 1;}

3. 搜索插入位置

35. 搜索插入位置 - 力扣（LeetCode）

?思路：二分查找，用左端點的模版，直接找到查找加返回要插入位置的值。如果未找到target，則檢查target是否大于nums[right]：如果是，插入位置為right + 1；否則，插入位置為right（即第一個大于等于target的位置）。

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left < right)  {int mid = left + (right - left) / 2;if(nums[mid] < target)left = mid + 1;elseright = mid;}if(target > nums[right])return right + 1;elsereturn right;}
};

4. x的平方根

69. x 的平方根 - 力扣（LeetCode）

直接將1 ~ x作為查找區間，找小于等于mid*mid的x的值

class Solution {
public:int mySqrt(int x) {if(x < 1) return 0;long long left = 0, right = x;while(left < right){long long mid = left + (right - left + 1) / 2;if(mid * mid <= x)left = mid;elseright = mid - 1;}return left;}
};

5. 山脈數組的峰頂索引

852. 山脈數組的峰頂索引 - 力扣（LeetCode）

?運用二分查找算法，因為在山脈數組中，在前一段山脈arr[mid] > arr[mid - 1]，在后一段山脈arr[mid] < arr[mid - 1]；根據這個二段性，使用二分查找。

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 0, right = arr.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(arr[mid] > arr[mid - 1])left = mid;elseright = mid - 1;}return left;}
};

6. 尋找峰值

162. 尋找峰值 - 力扣（LeetCode）

運用二分查找算法：對于區間中nums[i] 和 nums[i + 1]，如果nums[i] < nums[i + 1]，那么這段區間程上升趨勢，因為nums[-1]和nums[n] =?,所以在后一段區間內一定有峰值，讓left = mid + 1.

如果nums[i] > nums[i + 1]，程下降趨勢，在前一段區間內一定有峰值，讓right = mid。

class Solution {
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[mid + 1])right = mid;elseleft = mid + 1;}return left;}
};

7.尋找旋轉排序數組中的最小值

153. 尋找旋轉排序數組中的最小值 - 力扣（LeetCode）

?思路：使用二分查找，因為這個數組是有二段性的（要找的值為第二段的第一個元素），將這個數組分為兩段第一段的值一定比第二段的值大，所以根據nums[mid]和nums[n - 1]的關系作為比較。nums[mid]>nums[n - 1]，說明在mid第一段，所以要讓left = mid + 1；nums[mid] <= nums[n - 1]時，說明mid在第二段上，要讓right = mid。

第二種方法是一nums[0]作為比較值，只是這種有特殊情況，全是升序的時候會導致mid一直向后走，所以找特殊判斷一下升序的情況。

class Solution {
public:int findMin(vector<int>& nums) {/*int left = 0, right = nums.size() - 1, n = nums.size();while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[n - 1])left = mid + 1;elseright = mid;}return nums[right];*/int left = 0, right = nums.size() - 1, n = nums.size();if(nums[n - 1] > nums[0])return nums[0];while(left < right){int mid = left + (right - left) / 2;if(nums[mid] >= nums[0])left = mid + 1;elseright = mid;}return nums[right];}
};

8.點名

LCR 173. 點名 - 力扣（LeetCode）

?1.哈希表；2.直接遍歷找結構；3.位運算；4.求和公式。這些方法的時間復雜度都是O(N)。

方法5：二分查找：這個數組有二段性，分成兩段判斷對應的值是否相等，還需要處理一下全升序的情況

class Solution {
public:int takeAttendance(vector<int>& records) {int left = 0, right = records.size() - 1, n = records.size();if(records[n - 1] == n - 1)    return n;while(left < right){int mid = left + (right - left) / 2;if(records[mid] == mid)left = mid + 1;elseright = mid;}return right;}
};