LeetCode Hot100 ---- 二分查找专题
什么是二分查找
二分查找是計算機科學中最基本、最有用的算法之一。 它描述了在有序集合中搜索特定值的過程。
二分查找中使用的術語：
下面介紹三個常用的二分查找模板來源力扣：https://leetcode-cn.com/explore/learn/card/binary-search/
模板一：
模板1 這是最基礎的二分搜索模板，適合用來解決下列兩類問題：
（1）尋找有序數組中是否存在某個元素值;
（2）搜索條件中只涉及到訪問數組一個索引位置的元素，不涉及nums[mid]和其相鄰元素的比較
不適合處理邊界尋找問題，搜索區間為[left,right]左閉右閉區間，跳出循環后不需要任何后續的判斷操作，因為在每次循環中，都會檢查元素是否被找到，如果找到就返回。如果搜索到了最后，就說明元素沒有被找到，直接返回-1。
def binarySearch(nums, target):""":type nums: List[int]:type target: int:rtype: int"""if len(nums) == 0:return -1left, right = 0, len(nums) - 1while left <= right:mid = left + (right - left) // 2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1else:right = mid - 1# End Condition: left > rightreturn -1初始化條件：left = 0，right = len(nums)-1
循環維持條件：left <=?right （循環終止條件：left > right）
在左半部分數組搜索：right = mid -1
在右半部分數組搜索：left = mid + 1
模板二：
這個模板是實現二分搜索的高級形式，適合處理以下兩種問題：
（1）查找有序或部分有序數組中滿足某個條件的區間左邊界問題。
如在【leetcode-Python】- 二分搜索 - 153 Find Minimum in Rotated Sorted Array中，尋找旋轉有序數組的最小值相當于尋找數組中滿足x <= nums[-1]條件的第一個x，即求區間的左邊界問題。
（2）需要通過比較nums[mid]和nums[mid + 1] 來判斷局部單調性。
如在【leetcode-Python】-二分搜索-162 Find Peak Element中，由right暫存可能的Peak Element，通過一步步循環收緊搜索空間，最后當left和right相等時返回right或left。
?
搜索區間為[left,right)左閉右開區間，在left == right條件下跳出循環，因此在跳出循環后搜索空間中只有一個元素nums[left]，因此需要判斷這個元素是否滿足條件。
def binarySearch(nums, target):""":type nums: List[int]:type target: int:rtype: int"""if len(nums) == 0:return -1left, right = 0, len(nums)while left < right:mid = left + (right - left) // 2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1else:right = mid# Post-processing:# End Condition: left == rightif left != len(nums) and nums[left] == target:return leftreturn -1初始化條件：left = 0，right = len(nums)
循環維持條件：left? < right （循環終止條件：left == right）
在左半部分數組搜索：right = mid
在右半部分數組搜索：left = mid + 1
在一些問題中，由于在判斷左右區間的條件中涉及到對nums[right]的訪問(比如需要nums[mid]和nums[right]進行比較)，如果right初始化為len(nums)代碼會由于索引超出范圍而報錯。對于這種情況，這篇文章對leetcode網站上提供的模板進行了一點點修改。主要修改內容為以下兩點：
（1）將right變量的初始化數值由len(nums)改為len(nums) -1，這個修改會影響跳出循環后對nums[left]的檢驗方式，因為不需要檢驗left是否等于len(nums)，只需要判斷nums[left]是否和target相等即可。
（2）由于（1）中的修改，在跳出while循環的后處理中，將
修改為
return nums[left] == target ? left : -1 def binarySearch(nums, target):""":type nums: List[int]:type target: int:rtype: int"""if len(nums) == 0:return -1left, right = 0, len(nums) -1while left < right:mid = left + (right - left) // 2if nums[mid] < target:left = mid + 1else:right = midreturn nums[left] == target ? left : -1但是也存在一些特定的題目，需要將right初始化值設置為len(nums)或滿足搜索空間為[left,right)左閉右開區間的right值, 以避免在一些特例中出錯。如【leetcode-Python】- 二分類型 - 69 Sqrt(x)問題。
此外，如果nums數組中只有一個元素，將right初始化為len(nums)-1時，程序是不會進入while循環的（left == right == 0），因此要額外檢查跳出循環后程序對nums[left]的處理方式。并且對于left指針一直向右移動直到和right指針重合，即left = right = len(nums) - 1的情況，while循環跳出，此時nums[left]可被訪問，需要根據題目進行對應的判斷。
將right初始化改為len(nums)-1其實并不符合模板二搜索區間為[left,right)的設定，因此如果收縮搜索區間條件和nums[right]不相關，建議在leetcode提供的模板二的基礎上進行編寫（即初始化right為len(nums)）。
?
模板三：
是二分查找的另一種獨特形式。 它用于搜索需要訪問當前索引及其在數組中的直接左右鄰居索引的元素或條件。
搜索區間為(left,right)左開右開區間，因此以left = mid或right = mid的形式更新左右邊界（因為nums[mid] 本身就不滿足條件）。 在left + 1 == right條件下跳出循環，因為此時(left,right)左開右開區間為空。在后處理中對nums[left]和nums[right]都要進行檢驗。
?
初始化條件：left = 0，right = len(nums)-1
循環維持條件：left + 1 <??right （循環終止條件：left + 1 ==??right）
在左半部分數組搜索：right = mid
在右半部分數組搜索：left = mid
- LeetCode 556 下一個更大元素 III
- LeetCode 658 找到 K 個最接近的元素
- LeetCode 719 找出第 k 小的距離對
LeetCode 287 尋找重復數
給定一個包含?n + 1 個整數的數組?nums，其數字都在 1 到 n?之間（包括 1 和 n），可知至少存在一個重復的整數。假設只有一個重復的整數，找出這個重復的數。
- 不能更改原數組（假設數組是只讀的）。
- 只能使用額外的 O(1) 的空間。
- 時間復雜度小于 O(n^2) 。
- 數組中只有一個重復的數字，但它可能不止重復出現一次。
在這道題中，數的范圍是1~N，(數組長度為N+1)，由于要求空間復雜度為O(1)，同時原數組是只讀的，我們得考慮一個以時間換空間的方法
我們使用二分法，去把整個取值范圍拆成兩部分，[left, mid]和[mid+1, right]，然后計算[1, mid]出現的次數cnt
- 如果cnt > mid，說明重復的數出現在[left, mid]中，設right=mid
- 如果cnt <= mid，說明重復的數出現在[mid+1, right]中，設left=mid+1
不斷重復之后，最后當left=right時，找到的數就是重復數
find-minimum-in-rotated-sorted-array
假設按照升序排序的數組在預先未知的某個點上進行了旋轉，例如，數組 [0, 1, 2, 4, 5, 6, 7] 可能變為 [4, 5, 6, 7, 0, 1, 2]。請找出其中最小的元素。假設數組中無重復元素
使用二分搜索，當中間元素大于右側元素時意味著拐點即最小元素在右側，否則在左側
class Solution:def findMin(self, nums: List[int]) -> int:l , r = 0, len(nums) - 1while l < r:mid = l + (r - l) // 2if nums[mid] > nums[r]: # 數組有重復時，若 nums[l] == nums[mid] == nums[r]，無法判斷移動方向l = mid + 1else:r = midreturn nums[l]find-minimum-in-rotated-sorted-array-ii
假設按照升序排序的數組在預先未知的某個點上進行了旋轉，例如，數組 [0, 1, 2, 4, 5, 6, 7] 可能變為 [4, 5, 6, 7, 0, 1, 2]。請找出其中最小的元素。數組中可能包含重復元素。
class Solution:def findMin(self, nums: List[int]) -> int:l , r = 0, len(nums) - 1while l < r:mid = l + (r - l) // 2if nums[mid] > nums[r]:l = mid + 1elif nums[mid] < nums[r] or nums[mid] != nums[l]:r = midelse: # nums[l] == nums[mid] == nums[r]l += 1return nums[l]search-in-rotated-sorted-array
假設按照升序排序的數組在預先未知的某個點上進行了旋轉，例如，數組 [0, 1, 2, 4, 5, 6, 7] 可能變為 [4, 5, 6, 7, 0, 1, 2]。搜索一個給定的目標值，如果數組中存在這個目標值，則返回它的索引，否則返回 ?-1。假設數組中不存在重復的元素。
class Solution:def search(self, nums: List[int], target: int) -> int:l , r = 0, len(nums) - 1while l <= r:mid = l + (r - l) // 2if nums[mid] == target:return midelif nums[mid] > target:if nums[l] > target and nums[mid] > nums[r]:l = mid + 1else:r = mid - 1else:if nums[r] < target and nums[mid] < nums[l]:r = mid - 1else:l = mid + 1return -1search-in-rotated-sorted-array-ii
假設按照升序排序的數組在預先未知的某個點上進行了旋轉，例如，數組 [0, 0, 1, 2, 2, 5, 6] 可能變為 [2, 5, 6, 0, 0, 1, 2]。編寫一個函數來判斷給定的目標值是否存在于數組中，若存在返回 ?true，否則返回 ?false。數組中可能包含重復元素。
class Solution:def search(self, nums: List[int], target: int) -> int:l , r = 0, len(nums) - 1while l <= r:if nums[l] == nums[r] and nums[l] != target:l += 1r -= 1continuemid = l + (r - l) // 2if nums[mid] == target:return Trueelif nums[mid] > target:if nums[l] > target and nums[mid] > nums[r]:l = mid + 1else:r = mid - 1else:if nums[r] < target and nums[mid] < nums[l]:r = mid - 1else:l = mid + 1return False總結
以上是生活随笔為你收集整理的LeetCode Hot100 ---- 二分查找专题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 阿里云盘今晚出现故障，无法访问和加载内容
- 下一篇： 异地公积金转移好还是提取好 外地的公积金