1 二分查找

1.1 概念

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。

二分查找維護查找空間的左、右和中間指示符，并比較查找目標或將查找條件應用于集合的中間值；如果條件不滿足或值不相等，則清除目標不可能存在的那一半，并在剩下的一半上繼續查找，直到成功為止。如果查找以空的一半結束，則無法滿足條件，并且無法找到目標。

1.2 時間復雜度 O(log n)

假設總共有n個元素，則第一次查找剩余n/2個元素，第二次查找剩余n/2/2個元素，然后是n/2/2/2、n/2/2/2/2以此類推。

假設總共查找了k次，則剩余n/2^k個元素。最壞的情況是查找到最后一個元素，則有等式：n/2^k=1，即2^k=n，得：k=log₂n

忽略常數，則二分查找的時間復雜度為O(log n)

1.3 二分查找與順序查找對比圖

注：順序查找時間復雜度為O(n)

2 二分查找的一般步驟

• 第一步：如果集合未排序，則進行排序；

• 第二步：使用循環或遞歸在每次比較后將查找空間劃分為兩半；

• 第三步：在剩余空間中確定可行的候選者。

3 二分查找常用模板

3.1 模板1：搜索區間左閉右閉，基本的二分查找

int binarySearch(int[] nums, int target) {if (nums == null || nums.length == 0) return -1;int left = 0;int right = nums.length - 1;// 搜索區間為[left,right]，兩端都閉，nums.length 下標越界，故而使用最后一個元素的索引 nums.length - 1while (left <= right) {// 循環終止條件: left == right + 1，搜索區間為空，終止循環int mid = left + (right - left) / 2;// 防止(left + right)溢出if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;// 下一個搜索區間為[mid + 1,right]} else if (nums[mid] > target) {right = mid - 1;// 下一個搜索區間為[left,mid - 1]}}return -1; }

語法特點

• 初始條件：left = 0，right = length - 1
• 終止條件：left > right，即 left == right + 1
• 向左查找：right = mid - 1
• 向右查找：left = mid + 1

算法缺陷

比如 nums = [1,2,2,2,3]，target = 2，此算法返回的索引值為 2，雖然返回值沒錯，但是如果我想得到 target 的左側邊界，即索引值為 1；或者想得到 target 的右側邊界，即索引值為 3。這種情況依靠此算法是無法實現的。

3.2 模板2：搜索區間左閉右開，尋找左側邊界

int binarySearch(int[] nums, int target) {if (nums == null || nums.length == 0) return -1;int left = 0;int right = nums.length;// 搜索區間為[left,right)，左閉右開while (left < right) {// 循環終止條件: left == right，此時搜索區間[left,left)為空，終止循環int mid = left + (right - left) / 2;// 防止(left + right)溢出if (nums[mid] < target) {left = mid + 1;// 下一個搜索區間為[mid + 1,right)} else if (nums[mid] >= target) {right = mid;// 下一個搜索區間為[left,mid)}}if (left == nums.length) return -1;// target比所有數都大，返回-1return nums[left] == target ? left : -1;// 不存在該值則返回-1 }

語法特點

• 初始條件：left = 0，right = length
• 終止條件：left == right
• 向左查找：right = mid
• 向右查找：left = mid + 1

關鍵點

• 當nums[mid] == target時，并非立即返回，而是縮小搜索區間的上界 right，不斷向左收縮

• 需要后處理，當只剩下一個元素時，需要判斷元素是否符合條件

3.3 模板3：搜索區間左閉右開，尋找右側邊界

int binarySearch(int[] nums, int target) {if (nums == null || nums.length == 0) return -1;int left = 0;int right = nums.length;// 搜索區間為[left,right)，左閉右開while (left < right) {// 終止條件: left == right，此時搜索區間[left,left)為空，終止循環int mid = left + (right - left) / 2;// 防止(left + right)溢出if (nums[mid] <= target) {left = mid + 1;// 下一個搜索區間為[mid + 1,right)} else if (nums[mid] > target) {right = mid;// 下一個搜索區間為[left,mid)}}if (left == 0) return -1;// target比所有數都小，返回-1return nums[left - 1] == target ? (left - 1) : -1;// 不存在該值則返回-1 }

語法特點

• 初始條件：left = 0，right = length
• 終止條件：left == right
• 向左查找：right = mid
• 向右查找：left = mid + 1

關鍵點

• 當nums[mid] == target時，并非立即返回，而是增大搜索區間的下界left，不斷向右收縮

• 需要后處理，當只剩下一個元素時，需要判斷元素是否符合條件

4 二分查找相關題目（題目來源：Leetcode）

4.1 二分查找

4.1.1 題目描述

給定一個n個元素有序的（升序）整型數組nums和一個目標值target，寫一個函數搜索nums中的target，如果目標值存在返回下標，否則返回-1。

示例 1

輸入: nums = [-1,0,3,5,9,12], target = 9 輸出: 4 解釋: 9 出現在 nums 中并且下標為 4

示例 2

輸入: nums = [-1,0,3,5,9,12], target = 2 輸出: -1 解釋: 2 不存在 nums 中因此返回 -1

題目來源

• 704. 二分查找 - 力扣（Leetcode）

4.1.2 解題思路

基本的二分查找

4.1.3 Java 代碼實現

public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {// 等同于 (left + right) / 2，下面的寫法可以防止溢出int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {// 收縮右側邊界right = mid - 1;} else if (nums[mid] < target) {// 收縮左側邊界left = mid + 1;}}return -1; }

4.2 搜索插入位置

4.2.1 題目描述

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

請必須使用時間復雜度為O(log n)的算法。

示例 1

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

示例 2

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

示例 3

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

題目來源

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

4.2.2 解題思路

基本的二分查找，找不到值不返回-1，返回按順序插入的索引值

4.2.3 Java 代碼實現

public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {// 等同于 (left + right) / 2，下面的寫法可以防止溢出int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {// 收縮左側邊界left = mid + 1;} else if (nums[mid] > target) {// 收縮右側邊界right = mid - 1;}}// 目標值不存在數組中，此時下標 left 對應元素為數組中比 target 大的最小值，故按順序應將目標值插入 left 的位置return left; }

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

4.3.1 題目描述

給你一個按照非遞減順序排列的整數數組nums，和一個目標值target。請你找出給定目標值在數組中的開始位置和結束位置。

如果數組中不存在目標值target，返回[-1, -1]。

你必須設計并實現時間復雜度為O(log n)的算法解決此問題。

示例 1

輸入：nums = [5,7,7,8,8,10], target = 8 輸出：[3,4]

示例 2

輸入：nums = [5,7,7,8,8,10], target = 6 輸出：[-1,-1]

示例 3

輸入：nums = [], target = 0 輸出：[-1,-1]

題目來源

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

4.3.2 解題思路

二分查找，分別查出左右邊界值，然后組合返回

4.3.3 Java 代碼實現

public int[] searchRange(int[] nums, int target) {if (nums == null || nums.length == 0) {return new int[]{-1, -1};}// 找左側邊界int left = 0;int right = nums.length;while (left < right) {// 等同于 (left + right) / 2，下面的寫法可以防止溢出int mid = left + (right - left) / 2;if (nums[mid] >= target) {// 收縮右側邊界，左閉右開區間，不包含下標 right 對應的元素，所以直接將 mid 賦值給 right 即可right = mid;} else {// 收縮左側邊界left = mid + 1;}}// 后處理，當只剩下一個元素時，需要判斷元素是否符合條件if (left == nums.length || nums[left] != target) {// 數組中不存在該值return new int[]{-1, -1};}// 數組中存在該值，左側邊界為int leftVal = left;// 找右側邊界left = 0;right = nums.length;while (left < right) {// 等同于 (left + right) / 2，下面的寫法可以防止溢出int mid = left + (right - left) / 2;if (nums[mid] <= target) {// 收縮左側邊界left = mid + 1;} else {// 收縮右側邊界，左閉右開區間，不包含下標 right 對應的元素，所以直接將 mid 賦值給 right 即可right = mid;}}// 不需要后處理，因為前面尋找左側邊界時做過判斷了，能走到這里數組中必然存在該值，右側邊界為int rightVal = left - 1;return new int[]{leftVal, rightVal}; }

4.4 x 的平方根

4.4.1 題目描述

給你一個非負整數x，計算并返回x的算術平方根。

由于返回類型是整數，結果只保留整數部分，小數部分將被舍去。

注意：不允許使用任何內置指數函數和運算符，例如pow(x, 0.5)或者x ** 0.5。

示例 1

輸入：x = 4 輸出：2

示例 2

輸入：x = 8 輸出：2 解釋：8 的算術平方根是 2.82842..., 由于返回類型是整數，小數部分將被舍去。

題目來源

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

4.4.2 解題思路

對區間 [0, x] 進行二分查找，計算 (long) mid * mid 與 x 作比較（轉為long類型防止 int 類型值相乘后溢出），或者更換成除法操作 x / mid 與 mid 作比較防止溢出（需要排除一些特殊情況，避免除數 mid 為 0 的情況）。

注意：由于題干要求保留整數部分，所以 int 類型值相除后自動舍棄小數部分也能滿足要求，例如：5 / 2 == 2 在這個邏輯判斷里是合法的

4.4.3 Java 代碼實現

public int mySqrt(int x) {// 0或1直接返回，避免后面的除數mid為0if (x < 2) {return x;}int left = 0;int right = x;while (left <= right) {// 等同于 (left + right) / 2，下面的寫法可以防止溢出int mid = left + (right - left) / 2;// 更換成除法操作，防止溢出if (x / mid == mid) {return mid;} else if (x / mid > mid) {// 收縮左側邊界left = mid + 1;} else {// 收縮右側邊界right = mid - 1;}}// 走到這里說明 x 非完全平方數，此時下標 left 對應元素為數組中比 x 的算數平方根 大的最小整數值// 題干要求保留整數部分，舍去小數部分，故應該返回數組中比 x 的算數平方根 小的最大整數值，也就是 left - 1// while 循環的終止條件為 left = right + 1，所以 left - 1 等同于 rightreturn right; }

4.5 有效的完全平方數

4.5.1 題目描述

給你一個正整數num。如果num是一個完全平方數，則返回true，否則返回false 。

完全平方數是一個可以寫成某個整數的平方的整數。換句話說，它可以寫成某個整數和自身的乘積。

不能使用任何內置的庫函數，如sqrt。

示例 1

輸入：num = 16 輸出：true 解釋：返回 true ，因為 4 * 4 = 16 且 4 是一個整數。

示例 2

輸入：num = 14 輸出：false 解釋：返回 false ，因為 3.742 * 3.742 = 14 但 3.742 不是一個整數。

題目來源

• 367. 有效的完全平方數 - 力扣（Leetcode）

4.5.2 解題思路

對區間 [0, num] 進行二分查找，計算 mid * mid 與 num 作比較，相同則返回 true。

注意：要將 mid * mid 的結果轉為 long 類型，防止超過 int 類型最大值溢出；另此處不可以使用將 mid * mid == num 的判斷改為除法 num / mid == mid，因為計算參數都是 int 類型，結果會直接舍棄小數部分，造成錯誤計算，例如：5 / 2 == 2

4.5.3 Java 代碼實現

public boolean isPerfectSquare(int num) {int left = 0;int right = num;while (left <= right) {// 等同于 (left + right) / 2，下面的寫法可以防止溢出int mid = left + (right - left) / 2;// 強轉為 long 類型，防止 int 值溢出long square = (long) mid * mid;if (square == num) {return true;}if (square < num) {// 收縮左側邊界left = mid + 1;} else {// 收縮右側邊界right = mid - 1;}}return false; }

總結

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

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