整數二分步驟：
1.找一個區間[L,R],使答案一定在這個區間
2.找一個判斷條件，使得該判斷條件具有二段性(一般具有單調性)，并且答案一定是該二段性的分界點
3.分析終點M在該判斷條件下是否成立，如果成立，考慮答案在哪個區間，如果不成立，考慮答案在哪個區間
4.如果更新方式寫的是R = Mid，則不用做如何處理，如果更新方式寫的是L = Mid，則需要在計算Mid時加上1

核心操作：

while(r-l > 10e-7) {int mid = l+r+1>>1;if (check(mid)){l = mid;}else{r = mid-1;} }while (r-l > 10e-7) {int mid = l+r>>1;if (check(mid)){r = mid;}else{l = mid+1;} }

例子:
LeetCode 35:
給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。

你可以假設數組中無重復元素。

示例 1:

輸入: [1,3,5,6], 5
輸出: 2

示例 2:

輸入: [1,3,5,6], 2
輸出: 1

示例 3:

輸入: [1,3,5,6], 7
輸出: 4

示例 4:

輸入: [1,3,5,6], 0
輸出: 0

代碼如下:

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

總結

以上是生活随笔為你收集整理的整数二分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。