目錄

二分查找與分治

循環方式

遞歸方式

元素中有重復的二分查找

基于二分查找的拓展問題

山脈數組的頂峰索引——局部有序

旋轉數字中的最小數字

找缺失數字

優化平方根

中序與搜索樹

二叉搜索樹中搜索特定值

驗證二叉搜索樹

有序數組轉化為二叉搜索樹

尋找兩個有序數組中的中位數

---

凡是在排好序的地方查找的都就可以考慮用二分來優化查找效率。

不一定全局都排好才行，只要某個部分是排好的，就可以針對該部分進行二分查找，這是很多題目優化查找的重要途徑。

為了更有通用性，插值查找使用的公式是：

mid=low+(key- a[low])/(a[high]-a[low])*(high-low)

二分查找與分治

二分查找就是將中間結果與目標進行比較，一次去掉一半，因此二分查找可以說是最簡單、最典型的分治了。

循環方式

public static int binarySearch(int[] array, int low, int high, int target) {while (low <= high) {int mid = low + ((high - low) >> 1);if (array[mid] == target) {return mid;} else if (array[mid] > target) {// 由于array[mid]不是目標值，因此再次遞歸搜索時，可以將其排除high = mid - 1;} else {// 由于array[mid]不是目標值，因此再次遞歸搜索時，可以將其排除low = mid + 1;}}return -1;
}

遞歸方式

public  int binarySearch1(int[] array, int low, int high, int target) {//遞歸終止條件if(low <= high){int mid = low + ((high - low) >> 1);if(array[mid] == target){return mid  ;  // 返回目標值的位置，從1開始}else if(array[mid] > target){// 由于array[mid]不是目標值，因此再次遞歸搜索時，可以將其排除return binarySearch(array, low, mid-1, target);}else{// 由于array[mid]不是目標值，因此再次遞歸搜索時，可以將其排除return binarySearch(array, mid+1, high, target);}}return -1;   //表示沒有搜索到
}

元素中有重復的二分查找

假如在上面的基礎上，元素存在重復，如果重復則找左側第一個。

這里的關鍵是找到目標結果之后不是返回而是繼續向左側移動。第一種，也是最簡單的方式，找到相等位置向左使用線性查找，直到找到相應的位置。

public static int search(int[] nums, int target) {if (nums == null || nums.length == 0)return -1;int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {//找到之后，往左邊找while (mid != 0 && nums[mid] == target)mid--;if (mid == 0 && nums[mid] == target) {return mid;}    return mid + 1;}}return -1;
}

基于二分查找的拓展問題

山脈數組的頂峰索引——局部有序

在數組中的某位位置i開始，從0到i是遞增的，從i+1 到數組最后是遞減的，讓你找到這個最高點。

符合下列屬性的數組 arr 稱為山脈數組 ：arr.length >= 3存在 i（0 < i < arr.length - 1）使得：

• arr[0] < arr[1] < ... arr[i-1] < arr[i]

• arr[i] > arr[i+1] > ... > arr[arr.length - 1]

給你由整數組成的山脈數組 arr ，返回任何滿足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下標 i 。

這個題其實就是前面找最小值的相關過程而已，最簡單的方式是對數組進行一次遍歷。

當我們遍歷到下標i時，如果有arr[i-1]<arr[i]>arr[i+1],那么i就是我們需要找出的下標。

其實還可以更簡單一些，因為是從左開始找的，開始的時候必然是arr[i-1]<a[i],所以只要找到第一個arr[i]>arr[i+1]的位置即可。

public int peakIndexInMountainArray(int[] arr) {int n = arr.length;int ans = -1;for (int i = 1; i < n - 1; ++i) {if (arr[i] > arr[i + 1]) {ans = i;break;}}return ans;
}

對于二分的某一個位置 mid，mid 可能的位置有3種情況:

• mid在上升階段的時候，滿足arr[mid]>a[mid-1] && arr[mid]<arr[mid+1]

• mid在頂峰的時候，滿足arr[i]>a[i-1] && arr[i]>arr[i+1]

• mid在下降階段，滿足arr[mid]<a[mid-1] && arr[mid]>arr[mid+1]

因此我們根據 mid 當前所在的位置，調整二分的左右指針，就能找到頂峰。

public int peakIndexInMountainArray(int[] arr) {if (arr.length== 3)return 1;int left = 1, right = arr.length - 2;while(left < right) {int mid =left+ ((right - left)>>1);if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])return mid;if (arr[mid] < arr[mid + 1] && arr[mid] > arr[mid - 1])left = mid + 1;if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])right = mid - 1;}return left;
}

旋轉數字中的最小數字

已知一個長度為 n 的數組，預先按照升序排列，經由1到n次旋轉后，得到輸入數組。給你一個元素值 互不相同 的數組 nums ，它原來是一個升序排列的數組，并按上述情形進行了多次旋轉。請你找出并返回數組中的 最小元素 。

示例1：

輸入：nums = [4,5,1,2，3]

輸出：1

解釋：原數組為 [1,2,3,4,5] ，旋轉 3 次得到輸入數組。

示例2：

輸入：nums = [4,5,6,7,0,1,2]

輸出：0

解釋：原數組為 [0,1,2,4,5,6,7] ，旋轉 4 次得到輸入數組。

我們考慮數組中的最后一個元素 x：在最小值右側的元素（不包括最后一個元素本身），它們的值一定都嚴格小于 x；而在最小值左側的元素，它們的值一定都嚴格大于 x。因此，我們可以根據這一條性質，通過二分查找的方法找出最小值。

在二分查找的每一步中，左邊界為 low，右邊界為 high，區間的中點為 pivot，最小值就在該區間內。我們將中軸元素 nums[pivot] 與右邊界元素 nums[high] 進行比較，可能會有以下的三種情況：

第一種情況是nums[pivot]<nums[high]。如下圖所示，這說明nums[pivot] 是最小值右側的元素，因此我們可以忽略二分查找區間的右半部分。

public int findMin(int[] nums) {int low = 0;int high = nums.length - 1;while (low < high) {int pivot = low + ((high - low) >>1);if (nums[pivot] < nums[high]) {high = pivot;} else {low = pivot + 1;}}return nums[low];
}

找缺失數字

一個長度為n-1的遞增排序數組中的所有數字都是唯一的，并且每個數字都在范圍0～n-1之內。在范圍0～n-1內的n個數字中有且只有一個數字不在該數組中，請找出這個數字。

對于有序的也可以用二分查找，這里的關鍵點是在缺失的數字之前，必然有nums[i]==i，在缺失的數字之后，必然有nums[i]!=i。

因此，只需要二分找出第一個nums[i]!=i，此時下標i就是答案。若數組元素中沒有找到此下標，那么缺失的就是n。

public int missingNumber (int[] a) {int left = 0;int right = a.length-1;while(left < right){int mid = (left+right)/2;if(a[mid]==mid){left = mid+1;}else{right = mid-1;}}return left;
}

優化平方根

實現函數 int sqrt(int x)。計算并返回x的平方根這個題的思路是用最快的方式找到n*n=x的n。如果整數沒有平方根，一般采用向下取整的方式得到結果。

public int sqrt (int x) {int l=1,r=x;while(l <= r){int mid = l + ((r - l)>>1);if(x/mid > mid){l = mid + 1;} else if(x / mid < mid){r = mid - 1;} else  if(x/mid == mid){return mid;}}return r;
}

中序與搜索樹

如果一棵二叉樹是搜索樹，則按照中序遍歷其序列正好是一個遞增序列。

• 若它的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值;

• 若它的右子樹不空，則右子樹上所有節點的值均大于它的根節點的值;

• 它的左、右子樹也分別為二叉排序樹。

搜索樹的題目雖然也是用遞歸，但是與前后序有很大區別，主要是因為搜索樹是有序的，就可以根據條件決定某些遞歸就不必執行了，這也稱為“剪枝”。

二叉搜索樹中搜索特定值

給定二叉搜索樹（BST）的根節點和一個值。 你需要在BST中找到節點值等于給定值的節點。 返回以該節點為根的子樹。 如果節點不存在，則返回 NULL。

public TreeNode searchBST(TreeNode root, int val) {if (root == null || val == root.val) return root;return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}public TreeNode searchBST(TreeNode root, int val) {while (root != null && val != root.val)root = val < root.val ? root.left : root.right;return root;
}

驗證二叉搜索樹

給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜索樹。

有效 二叉搜索樹定義如下：

• 節點的左子樹只包含 小于 當前節點的數。

• 節點的右子樹只包含 大于 當前節點的數。

• 所有左子樹和右子樹自身必須也是二叉搜索樹。

結合二叉搜索樹的性質，中序遍歷構成的序列一定是升序的。在中序遍歷的時候實時檢查當前節點的值是否大于前一個中序遍歷到的節點的值即可。

long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 如果左子樹下某個元素不滿足要求，則退出if (!isValidBST(root.left)) {return false;}// 訪問當前節點：如果當前節點小于等于中序遍歷的前一個節點，說明不滿足BST，返回 false；否則繼續遍歷。if (root.val <= pre) {return false;}pre = root.val;// 訪問右子樹return isValidBST(root.right);
}

有序數組轉化為二叉搜索樹

給你一個整數數組 nums ，其中元素已經按 升序 排列，請你將其轉換為一棵 高度平衡 二叉搜索樹。

理論上如果要構造二叉搜索樹，可以以升序序列中的任一個元素作為根節點，以該元素左邊的升序序列構建左子樹，以該元素右邊的升序序列構建右子樹，這樣得到的樹就是一棵二叉搜索樹。 本題要求高度平衡，因此我們需要選擇升序序列的中間元素作為根節點，這本質上就是二分查找的過程。

class Solution {public TreeNode sortedArrayToBST(int[] nums) {return helper(nums, 0, nums.length - 1);}public TreeNode helper(int[] nums, int left, int right) {if (left > right) {return null;}// 總是選擇中間位置左邊的數字作為根節點int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = helper(nums, left, mid - 1);root.right = helper(nums, mid + 1, right);return root;}
}

尋找兩個有序數組中的中位數

給定兩個大小分別為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。請你找出并返回這兩個正序數組的中位數 。

首先，中位數到底是什么？

• 如果合并后的數組長度是奇數，中位數就是中間那個數（比如總長度7，中位數是第4個數）。

• 如果是偶數，中位數是中間兩個數的平均值（比如總長度8，中位數是第4和第5個數的平均）。

所以問題可以轉化為：如何找到兩個有序數組中第k小的數，其中k可能是(m+n)/2或(m+n)/2+1。

二分思想延伸思路：每次排除不可能的部分 假設我們要找第k小的數，可以比較兩個數組中第k/2位置的元素：

• 比如k=5，我們比較nums1的第2個元素（k/2=2，索引從0開始是1）和nums2的第2個元素。

• 如果nums1的這個元素更小，說明nums1的前k/2個元素都不可能是第k小的數，可以排除掉這部分，問題規模就縮小了一半！

舉個栗子🌰： nums1 = [1,3,5], nums2 = [2,4,6], 找第4小的數（k=4）。

1. 比較nums1的第2個元素（k/2=2，即nums1[1]=3）和nums2的第2個元素（nums2[1]=4）。

2. 3 < 4 → 排除nums1的前2個元素（1和3），現在nums1剩下[5]。

3. 問題變成從[5]和[2,4,6]中找第4-2=2小的數。

4. 現在k=2，比較剩下的數組的第1個元素（k/2=1）：

   1. nums1[0]=5 vs nums2[0]=2 → 2更小，排除nums2的前1個元素（2）。

5. 現在問題變成從[5]和[4,6]中找第2-1=1小的數，即最小的數：4。

6. 所以第4小的數是4。

邊界情況怎么辦？

• 如果某個數組長度不夠k/2： 比如nums1只剩2個元素，但k/2=3，這時候只能取nums1剩下的所有元素，排除掉這部分后k減去實際排除的數量。

• 當k=1時： 直接比較兩個數組當前剩下的第一個元素，取較小的那個。

• 一個數組被完全排除： 直接在另一個數組中找第k小的數。

為什么能保證時間復雜度是O(log(m+n))？ 每次排除掉k/2個元素，相當于每次將問題規模減半，類似二分查找，所以時間復雜度是對數級別的。

再舉個栗子🌰（處理邊界）： nums1 = [1,2], nums2 = [3,4]，找第3小的數（總長度4，中位數是第2和3的平均）。

1. 找第3小的數：k=3。

2. 比較nums1的第1個元素（k/2=1，nums1[0]=1）和nums2的第1個元素（nums2[0]=3）。

3. 1 < 3 → 排除nums1的前1個元素（1），k=3-1=2。

4. 現在nums1剩下[2]，nums2是[3,4]。

5. 找第2小的數：比較nums1[0]=2和nums2[0]=3 → 2更小，排除nums1的1個元素，k=2-1=1。

6. 現在k=1，取剩下數組的第一個元素：nums2[0]=3。

7. 所以第3小的是3，中位數是(2+3)/2=2.5。

總結步驟：

1. 始終保持nums1是較短的數組（減少邊界處理）。

2. 遞歸或循環比較兩個數組的k/2位置：

   1. 排除較小元素的前半部分。

   2. 更新k值（減去排除的數量）。

3. 處理邊界（數組長度不足、k=1等）。

通過不斷排除不可能的部分，最終就能高效找到第k小的數啦！雖然細節有點多，但多舉例子就能理解啦~ (??????)??

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int length1 = nums1.length, length2 = nums2.length;int totalLength = length1 + length2;if (totalLength % 2 == 1) {int midIndex = totalLength / 2;double median = getKthElement(nums1, nums2, midIndex + 1);return median;} else {int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;return median;}}public int getKthElement(int[] nums1, int[] nums2, int k) {int length1 = nums1.length, length2 = nums2.length;int index1 = 0, index2 = 0;while (true) {// 邊界情況if (index1 == length1) {return nums2[index2 + k - 1];}if (index2 == length2) {return nums1[index1 + k - 1];}if (k == 1) {return Math.min(nums1[index1], nums2[index2]);}// 正常情況int half = k / 2;int newIndex1 = Math.min(index1 + half, length1) - 1;int newIndex2 = Math.min(index2 + half, length2) - 1;int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];if (pivot1 <= pivot2) {k -= (newIndex1 - index1 + 1);index1 = newIndex1 + 1;} else {k -= (newIndex2 - index2 + 1);index2 = newIndex2 + 1;}}}
}