二分法

• 前言
• 69. x 的平方根
• 35. 搜索插入位置

前言

二分查找也常被稱為二分法或者折半查找，每次查找時(shí)通過將待查找區(qū)間分成兩部分并只取一部分繼續(xù)查找，將查找的復(fù)雜度大大減少。對于一個(gè)長度為 O(n) 的數(shù)組，二分查找的時(shí)間復(fù)雜度為 O(log n)。

69. x 的平方根

題解
我們可以把這道題想象成，給定一個(gè)非負(fù)整數(shù) $a$，求$f(x)=x2,a=0$ 的解。因?yàn)槲覀冎豢紤] $x\ge 0$，所以 $f(x)$ 在定義域上是單調(diào)遞增的?？紤]到 $f(0)=a\le 0，f(a)=a2a\ge 0$，我們可以對 $[0,a]$ 區(qū)間使用二分法找到 $f(x)=0$ 的解。

代碼

class Solution { public:int mySqrt(int x) {if(x == 1)return 1;int min = 0;int max = x;while(max-min>1){int m = (max+min)/2;if(x/m<m)max = m;elsemin = m;}return min;} };

35. 搜索插入位置

題解
例如到底是 $while(left<right)$ 還是 $while(left<=right)$，到底是$right=middle$呢，還是要$right=middle?1$呢？

這里弄不清楚主要是因?yàn)?*「對區(qū)間的定義沒有想清楚，這就是不變量」**。

要在二分查找的過程中，保持不變量，這也就是**「循環(huán)不變量」**。

代碼

class Solution { public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int left = 0;int right = n - 1; // 定義target在左閉右閉的區(qū)間里，[left, right] while (left <= right) { // 當(dāng)left==right，區(qū)間[left, right]依然有效int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // target 在左區(qū)間，所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1; // target 在右區(qū)間，所以[middle + 1, right]} else { // nums[middle] == targetreturn middle;}}// 分別處理如下四種情況// 目標(biāo)值在數(shù)組所有元素之前 [0, -1]// 目標(biāo)值等于數(shù)組中某一個(gè)元素 return middle;// 目標(biāo)值插入數(shù)組中的位置 [left, right]，return right + 1// 目標(biāo)值在數(shù)組所有元素之后的情況 [left, right]， return right + 1return right + 1;} };

總結(jié)

以上是生活随笔為你收集整理的二分法（leetcode分类解题，C++代码详细注释）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。