搜索插入位置

給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。
請必須使用時間復雜度為 O(log n) 的算法。
示例 1:
輸入: nums = [1,3,5,6], target = 5
輸出: 2
示例 2:
輸入: nums = [1,3,5,6], target = 2
輸出: 1

代碼：
閉區間解法

class Solution {public int searchInsert(int[] nums, int target) {int left = 0, right = nums.length - 1;while(left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {right = mid - 1;} else {left = mid + 1;}}return left;}
}

搜索二維矩陣

給你一個滿足下述兩條屬性的 m x n 整數矩陣：

• 每行中的整數從左到右按非嚴格遞增順序排列。
• 每行的第一個整數大于前一行的最后一個整數。

給你一個整數 target ，如果 target 在矩陣中，返回 true ；否則，返回 false 。

思路
把該二維矩陣設想成一個一維的有序數組，那么在該一維數組的第 $i$ 個位置的數可以用二維矩陣 ( m 行 n 列) 表示，即在 $i/n$ 行，$i\%n$ 列.

代碼
在上一題的基礎上修改代碼：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;int left = 0, right = m*n-1;while(left <= right) {int mid = left + (right - left) / 2;int val = matrix[mid/n][mid%n];if (val == target) {return true;} else if(val < target) {left = mid + 1;} else {right = mid - 1;}}return false;}
}

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

給你一個按照非遞減順序排列的整數數組 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]

思路
用兩次二分查找分別找左邊界和有邊界
第一次二分法找左邊界，第二次二分法找右邊界

代碼
先初始化左邊界有邊界為 -1

class Solution {public int[] searchRange(int[] nums, int target) {int left = 0, right = nums.length - 1;int leftBoard = -1, rightBoard = -1;// 尋找左邊界while(left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {leftBoard = mid; right = mid - 1;  // 找到之后 在 mid 的左邊區間繼續找，直到找到最左邊的邊界} else if(nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}left = 0;right = nums.length - 1;// 尋找右邊界while(left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {rightBoard = mid;left = mid + 1;} else if(nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return new int[]{leftBoard, rightBoard};}
}

尋找旋轉排序數組中的最小值

已知一個長度為 n 的數組，預先按照升序排列，經由 1 到 n 次 旋轉 后，得到輸入數組。例如，原數組 nums = [0,1,2,4,5,6,7] 在變化后可能得到：
若旋轉 4 次，則可以得到 [4,5,6,7,0,1,2]
若旋轉 7 次，則可以得到 [0,1,2,4,5,6,7]
注意，數組 [a[0], a[1], a[2], …, a[n-1]] 旋轉一次 的結果為數組 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
給你一個元素值 互不相同 的數組 nums ，它原來是一個升序排列的數組，并按上述情形進行了多次旋轉。請你找出并返回數組中的 最小元素 。
你必須設計一個時間復雜度為 O(log n) 的算法解決此問題。
示例 1：
輸入：nums = [3,4,5,1,2]
輸出：1
解釋：原數組為 [1,2,3,4,5] ，旋轉 3 次得到輸入數組。
示例 2：
輸入：nums = [4,5,6,7,0,1,2]
輸出：0
解釋：原數組為 [0,1,2,4,5,6,7] ，旋轉 3 次得到輸入數組。

思路
設 x=nums[mid] 是現在二分取到的數。
我們需要判斷 x 和數組最小值的位置關系，誰在左邊，誰在右邊？
把 x 與最后一個數 nums[n?1] 比大小：

• 如果 x>nums[n?1]，那么可以推出以下結論：
  • nums 一定被分成左右兩個遞增段；
  • 第一段的所有元素均大于第二段的所有元素；
  • x 在第一段。
  • 最小值在第二段。
  • 所以 x 一定在最小值的左邊。
• 如果 x≤nums[n?1]，那么 x 一定在第二段。（或者 nums 就是遞增數組，此時只有一段。）
  • x 要么是最小值，要么在最小值右邊。

所以，只需要比較 x 和 nums[n?1] 的大小關系，就間接地知道了 x 和數組最小值的位置關系，從而不斷地縮小數組最小值所在位置的范圍，二分找到數組最小值。

代碼

class Solution {public int findMin(int[] nums) {int n = nums.length;int left = 0, right = n - 2;while(left <= right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[n - 1]) {left = mid + 1;} else {right = mid - 1;}}return nums[left];}
}

搜索旋轉排序數組

整數數組 nums 按升序排列，數組中的值 互不相同 。
在傳遞給函數之前，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉，使數組變為 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下標 從 0 開始 計數）。例如， [0,1,2,4,5,6,7] 在下標 3 處經旋轉后可能變為 [4,5,6,7,0,1,2] 。
給你 旋轉后 的數組 nums 和一個整數 target ，如果 nums 中存在這個目標值 target ，則返回它的下標，否則返回 -1 。
你必須設計一個時間復雜度為 O(log n) 的算法解決此問題。
示例 1：
輸入：nums = [4,5,6,7,0,1,2], target = 0
輸出：4
示例 2：
輸入：nums = [4,5,6,7,0,1,2], target = 3
輸出：-1

思路
使用上一題的思路，先找到該旋轉排序數組的最小值的位置，然后根據 target 和 旋轉的位置（旋轉排序數組的最后一個數）的大小進行比較，判斷是在左邊查找還是在右邊查找。

代碼

class Solution {public int search(int[] nums, int target) {int min = findMin(nums);  // 先找到最小值的下標int n = nums.length;if (target == nums[n -1]) {return n - 1;   // 相等的話直接返回} else if (target > nums[n-1]) {return searchTarget(nums, target, 0, min - 1);  // 在左邊查找} else { return searchTarget(nums, target, min, n - 2);  // 在右邊查找}}// 查找最小值下標public int findMin(int[] nums) {int n = nums.length;int left = 0, right = n - 2;while( left <= right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[n - 1]) {left = mid + 1;} else {right = mid - 1;}}return left;}// 二分查找public int searchTarget(int[] nums, int target, int left, int right) {int n = nums.length;while(left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {right = mid - 1; } else {left = mid + 1;}}return -1;}
}

尋找兩個正序數組的中位數（hard）

給定兩個大小分別為 m 和 n 的正序（從小到大）數組 nums1 和 nums2。請你找出并返回這兩個正序數組的 中位數 。
算法的時間復雜度應該為 O(log (m+n)) 。
示例 1：
輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數組 = [1,2,3] ，中位數 2
示例 2：
輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并數組 = [1,2,3,4] ，中位數 (2 + 3) / 2 = 2.5

思路
我們將通過 二分查找 來解決這個問題，具體步驟如下：

1. 確保 nums1 是較短的數組

• 由于我們要在較短的數組上進行二分查找，為了減少計算復雜度，我們首先確保 nums1 的長度小于或等于 nums2。如果 nums1 的長度大于 nums2，我們交換這兩個數組。
• 這樣做的目的是保證二分查找的次數最小化，最大化效率。

2. 分割數組

• 我們的目標是將兩個數組分割成左右兩部分，使得合并后的兩個部分的元素個數相同，或者左邊多一個元素（如果總長度是奇數）。具體來說，假設 nums1 的長度是 n，nums2 的長度是 m，則：
  • 左邊部分的元素個數應為 (n + m + 1) / 2，這個值可以保證左邊部分最多比右邊部分多一個元素（當總長度是奇數時）。
  • 右邊部分的元素個數為 n + m - (n + m + 1) / 2。

3. 二分查找

• 在 nums1 上執行二分查找，假設當前查找的分割位置是 partition1，那么 nums1 的左邊部分就是 nums1[0]…nums1[partition1-1]，右邊部分是 nums1[partition1]…nums1[n-1]。
• 同樣地，nums2 的分割位置 partition2 可以通過以下公式計算：
  $partition2=(n+m+1)/2?partition1$
  這個公式確保了左邊部分的總元素個數為 (n + m + 1) / 2。

4. 確保分割符合條件

• 為了保證左邊部分的所有元素都小于或等于右邊部分的所有元素，我們需要檢查：
  • nums1[partition1 - 1] <= nums2[partition2]（nums1 左邊的最大值小于 nums2 右邊的最小值）。
  • nums2[partition2 - 1] <= nums1[partition1]（nums2 左邊的最大值小于 nums1 右邊的最小值）。
    如果這些條件成立，說明我們找到了合適的分割位置。

5. 計算中位數

• 如果兩個數組的總長度是奇數，中位數就是左邊部分的最大值，max(nums1[partition1 - 1], nums2[partition2 - 1])。
• 如果兩個數組的總長度是偶數，中位數是左邊部分的最大值和右邊部分的最小值的平均值：
  $median=(max(nums1[partition1?1],nums2[partition2?1])+min(nums1[partition1],nums2[partition2]))/2$

6. 二分查找的調整

• 如果不滿足條件，意味著 partition1 需要調整：
  • 如果 nums1[partition1 - 1] > nums2[partition2]，則需要將 partition1 向左移，即減小 partition1。
  • 如果 nums2[partition2 - 1] > nums1[partition1]，則需要將 partition1 向右移，即增大 partition1。

7. 邊界條件

• 對于數組的邊界，我們使用 Integer.MIN_VALUE 和 Integer.MAX_VALUE 來處理數組分割的邊界情況。例如，如果 partition1 為 0，意味著 nums1 左邊部分沒有元素，我們將 maxLeft1 設置為 Integer.MIN_VALUE；如果 partition1 為 n，意味著 nums1 右邊部分沒有元素，我們將 minRight1 設置為 Integer.MAX_VALUE。

代碼

public class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 保證 nums1 是較短的數組if (nums1.length > nums2.length) {int[] temp = nums1;nums1 = nums2;nums2 = temp;}int n = nums1.length;int m = nums2.length;// 在 nums1 上進行二分查找int left = 0, right = n;while (left <= right) {int partition1 = (left + right) / 2;int partition2 = (n + m + 1) / 2 - partition1;// 獲取 nums1 和 nums2 中的元素int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];int minRight1 = (partition1 == n) ? Integer.MAX_VALUE : nums1[partition1];int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];int minRight2 = (partition2 == m) ? Integer.MAX_VALUE : nums2[partition2];// 檢查是否找到合適的分割位置if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {// 如果數組長度是奇數if ((n + m) % 2 == 1) {return Math.max(maxLeft1, maxLeft2);} else {// 如果數組長度是偶數return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;}} else if (maxLeft1 > minRight2) {// 如果 maxLeft1 太大，調整左邊界right = partition1 - 1;} else {// 如果 maxLeft2 太大，調整右邊界left = partition1 + 1;}}return 0.0;}
}