[二分查找] 二：二分查找的经典例题
1.何時應(yīng)該會使用二分查找
- 當(dāng)題目中出現(xiàn)有序數(shù)組時
- 當(dāng)時間復(fù)雜度要求為log(n)時
- 搜索范圍可以一次縮小一半時
2. 經(jīng)典例題1
給定一個排序數(shù)組和一個目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置。
請必須使用時間復(fù)雜度為 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
示例 4:
輸入: nums = [1,3,5,6], target = 0
輸出: 0
示例 5:
輸入: nums = [1], target = 0
輸出: 0
此題為最經(jīng)典的二分查找
int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size();while(left < right){int mid = (left+right)/2;if(target == nums[mid]) return mid;else if(target > nums[mid]){left = mid + 1;}else {right = mid;}}return left; }3. 經(jīng)典例題2
整數(shù)數(shù)組 nums 按升序排列，數(shù)組中的值互不相同。
在傳遞給函數(shù)之前，nums 在預(yù)先未知的某個下標(biāo)k（0 <= k < nums.length）上進(jìn)行了 旋轉(zhuǎn)，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標(biāo) 從 0 開始 計數(shù)）。
例如， [0,1,2,4,5,6,7] 在下標(biāo) 3 處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2] 。
給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個整數(shù) target ，如果 nums 中存在這個目標(biāo)值 target ，則返回它的下標(biāo)，否則返回 -1 。要求時間復(fù)雜度為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
示例 3：
輸入：nums = [1], target = 0
輸出：-1
題目要求我們的時間復(fù)雜度為log(n)，所以我們很快能想到和二分查找有關(guān)。數(shù)組nums一開始為有序的，但是經(jīng)過旋轉(zhuǎn)之后不再整體有序，變成了兩個有序的部分。
這種情況下我們每次二分先檢查有序的那一半（至少有一半是有序的），如果要找的值正好在有序的這部分（比較左右邊界即可判斷出目標(biāo)值是否在有序部分），則收縮邊界，再進(jìn)行二分查找。如果不在有序的部分，則再考慮無序的部分，無序的部分可以再分為兩個部分，其中又有一半一定是有序的，剩下的步驟與前面一樣
int search(vector<int>& nums, int target) {int left = 0, right = nums.size()-1;while(left <= right){int mid = (left+right)/2;if(nums[mid] == target) return mid;//說明mid左邊有序if(nums[mid] >= nums[left]){//判斷目標(biāo)值是否在有序部分if(nums[mid] > target && nums[left] <= target){right = mid - 1;}else left = mid + 1;}//說明mid右邊有序else{//判斷目標(biāo)值是否在有序部分if(nums[mid] < target && nums[right] >= target){left = mid + 1;}else right = mid - 1;}}return -1; }3. 經(jīng)典例題3
給定兩個大小分別為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。請你找出并返回這兩個正序數(shù)組的 中位數(shù) 。
算法的時間復(fù)雜度應(yīng)該為 O(log (m+n)) 。
示例 1：
輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并數(shù)組 = [1,2,3] ，中位數(shù) 2
示例 2：
輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并數(shù)組 = [1,2,3,4] ，中位數(shù) (2 + 3) / 2 = 2.5
示例 3：
輸入：nums1 = [0,0], nums2 = [0,0]
輸出：0.00000
示例 4：
輸入：nums1 = [], nums2 = [1]
輸出：1.00000
示例 5：
輸入：nums1 = [2], nums2 = []
輸出：2.00000
兩個數(shù)組長度是固定的，所以中位數(shù)的位置也是固定的。當(dāng)兩數(shù)組長度之和為奇數(shù)時，中位數(shù)下標(biāo)為：(totalLength + 1) / 2，若為偶數(shù)，中位數(shù)為 (nums[totalLength / 2] + nums[(totalLength + 1) / 2])/2
要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進(jìn)行比較
- 這里的 “/” 表示整除
- nums1 中小于等于 pivot1 的元素有 nums1[0 … k/2-2] 共計 k/2-1 個
- nums2 中小于等于 pivot2 的元素有 nums2[0 … k/2-2] 共計 k/2-1 個
- 取 pivot = min(pivot1, pivot2)，兩個數(shù)組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個，這樣 pivot 本身最大也只能是第 k-1 小的元素
- 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 “刪除”，剩下的作為新的 nums1 數(shù)組
- 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 “刪除”，剩下的作為新的 nums2 數(shù)組
- 由于我們 “刪除” 了一些元素（這些元素都比第 k 小的元素要小），因此需要修改 k 的值，減去刪除的數(shù)的個數(shù)，搜索區(qū)間每次縮短了一半 k=k-k/2。
總結(jié)
以上是生活随笔為你收集整理的[二分查找] 二：二分查找的经典例题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [二分查找] 一：子区间界限应当如何确定
- 下一篇： Linux虚拟内存与线性地址翻译