使用二分查找法的前提：（1）數組為有序數組.

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）數組中無重復元素.

二分的兩種寫法：

方法一：[left，right]

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

方法二：[left,rigght）

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

核心代碼（遞歸）

int binsearch(int left,int right)

????????{

? ? ? ? ? ? ? ? if(left<=right)

????????????????????????{

? ? ? ? ????????? ? ????????int mid=(left+right)/2;

? ? ? ? ? ? ????????????????if(nums[mid]==target)

? ? ? ? ? ? ? ? ? ? ? ? ? ? return mid;

? ? ? ? ? ? ????????????????if(nums[mid]>target)

? ? ? ? ? ? ? ? ? ? ? ? ? ? return binsearch(left,mid-1);

? ? ? ? ? ? ????????????????if(nums[mid]<target)

? ? ? ? ? ? ? ? ? ? ? ? ? ??return binsearch(mid+1,right);

????????????????????????}

? ? ? ? ? ? ????????return 0;

? ? ? ? }

核心代碼（循環）

int f=-1;

while(left<=right)

{

? ? ? ? int mid=(left+right)/2;

????????if(nums[mid]==target)

????????{

????????????????f=mid;

????????????????break;

????????}

????????if(target<nums[mid])

????????right=mid-1;

????????if(target>nums[mid])

????????left=mid+1

}

? ? ? ? if(f==-1)

????????cout<<"沒找到";

? ? ? ? ?else

???????? cout<<f<<endl;

以下是力扣二分法題目的常見解題思路：
?

704. 二分查找
?
- 初始化左右指針?left?和?right?，分別指向數組兩端。
- 在?left <= right?的循環中，計算中間索引?mid?。
- 比較?nums[mid]?與?target?，若相等則返回?mid?；若?nums[mid] > target?，則更新?right = mid - 1?；若?nums[mid] < target?，則更新?left = mid + 1?。
- 循環結束未找到則返回-1。
?
35. 搜索插入位置
?
- 同樣以?left?和?right?初始化數組兩端。
- 循環條件為?left <= right?，計算?mid?后，若?nums[mid] >= target?，則?right = mid - 1?，否則?left = mid + 1?。
- 循環結束后，?left?所指位置就是目標值應插入的位置。
?
34. 在排序數組中查找元素的第一個和最后一個位置
?
- 先通過二分法找目標值第一個位置，當?nums[mid] >= target?時，更新?right = mid?，循環結束后?left?可能是第一個位置，需再判斷?nums[left]?是否為?target?。
- 找最后一個位置時，當?nums[mid] <= target?時，更新?left = mid?，循環結束后，若?nums[right]?是?target?，?right?就是最后一個位置。
?
69. x的平方根
?
- 令?left = 0?，?right = x?，在?left <= right?循環中計算?mid?。
- 若?mid * mid <= x && (mid + 1) * (mid + 1) > x?，則?mid?就是所求平方根；若?mid * mid > x?，更新?right = mid - 1?；否則更新?left = mid + 1?。
?
367. 有效的完全平方數
?
- 類似求平方根，?left?設為1，?right?設為?num?。
- 循環中計算?mid?，若?mid * mid == num?，則返回?true?；若?mid * mid > num?，更新?right = mid - 1?，否則更新?left = mid + 1?。循環結束未找到則返回?false?。
?
162. 尋找峰值
?
- 初始化?left = 0?，?right = nums.length - 1?。
- 當?left < right?時，計算?mid?，若?nums[mid] > nums[mid + 1]?，說明峰值在左半部分，更新?right = mid?；否則峰值在右半部分，更新?left = mid + 1?。
- 循環結束后，?left?指向的就是一個峰值位置。

判斷?right?應賦值為?mid?還是?mid - 1?

關鍵在于二分查找的目標以及當前中間值與目標值的關系，具體可從以下幾方面判斷：
?
- 查找精確值且數組元素唯一：當目標是在有序數組中查找某個精確值，且數組元素唯一時，若?nums[mid] > target?，說明目標值在左半部分，此時應將?right?賦值為?mid - 1?。因為?nums[mid]?已經大于?target?，它不可能是目標值，所以下一輪查找范圍應不包含?mid?，如704. 二分查找就是這種情況。
?
- 查找左邊界或最大不超過目標值的元素：若要查找目標值在數組中的左邊界，或者是查找數組中最大的、不超過目標值的元素時，當?nums[mid] >= target?，應將?right?賦值為?mid?。這是為了讓查找范圍繼續向左側收縮，且保留?mid?位置，因為?mid?位置有可能就是左邊界，或者是符合條件的最大元素，如35. 搜索插入位置、34. 查找元素第一個位置就需這樣處理。
?
- 查找右邊界或最小超過目標值的元素：當任務是查找目標值的右邊界，或者是要找到數組中最小的、超過目標值的元素時，若?nums[mid] <= target?，則應將?right?賦值為?mid - 1?。這樣能使查找范圍向右收縮，同時排除?mid?位置，因為?mid?位置及左側元素已不滿足“右邊界”或“最小超過目標值”的條件，例如34. 查找元素最后一個位置時就遵循此規則。

二分法是一種通過不斷將區間一分為二，逐步逼近目標值的算法方法，適用于以下幾類題型：

-方程求解類：用于求解方程f(x)=0的根。若函數f(x)在區間[a,b]上連續，且f(a)\cdot f(b)<0，則可利用二分法在該區間內尋找方程的根。如求解方程x^3 - 2x - 1 = 0在區間[1,2]內的根。
?
- 函數最值類：當函數f(x)在某區間上具有單調性，且已知最值所在的大致區間時，可通過二分法來逼近最值。例如，求函數f(x)=x^2 - 4x + 3在區間[0,3]上的最小值，可利用二分法不斷縮小包含最小值的區間。
?
- 數據查找類：常用于在有序數組中查找特定元素。如在一個按升序排列的整數數組?[1, 3, 5, 7, 9, 11]?中查找數字7，可使用二分法，每次將數組分成兩部分，確定目標元素在左半部分還是右半部分，逐步縮小查找范圍。
?
- 參數確定類：一些問題中需要確定某個參數的取值，使得某個條件成立。若該條件與參數之間存在單調關系，可借助二分法確定參數值。比如，在物理實驗中，要確定一個電阻值，使得電路中的電流滿足某個范圍，已知電流與電阻成反比例關系，就可通過二分法來嘗試不同電阻值，找到符合條件的電阻。
?
- 最優解搜索類：在一些組合優化問題中，若目標函數具有單調性或滿足一定的條件，可利用二分法搜索最優解。如背包問題中，已知背包容量和物品重量價值，二分查找能裝入背包的最大價值對應的重量限制，進而求解最優裝包方案。