例題
給定一個排序數組和一個目標值,在數組中找到目標值,并返回其索引。如果目標值不存在于數組中,返回它將會被按順序插入的位置。
請必須使用時間復雜度為 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
思路
典型的二分查找問題,但是怎么樣將這個代碼寫得優雅?怎樣將問題思考得簡潔,能解決問題并且沒有邊界條件得疏漏?怎么樣再每次遇到二分查找問題時都能以一種思路優雅而正確地寫出代碼?
下面是這道題的代碼:
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:l = 0r = len(nums)-1while(l <= r):mid = (l+r) // 2if(nums[mid] < target):l = mid + 1else:r = mid - 1return l
非常優雅,無需判定任何邊界條件。有多種方法可以證明這個方法的正確性,有的過于繁瑣,以至于在每次編寫二分查找代碼時,都要進行繁復的思考,花費時間且可能出錯。
下面是一種優雅的思考方法,我稱之為:收斂+條件:
- 每一次循環,必然導致端點移動,因此不會出現死循環問題,也就是必定有解
- 本題是找出第一個≥target的元素,l只會向右移動,初始l=0,且每次l都在<target的情況下。向右移動一個元素,因此l肯定不會突破約束
- 退出時的狀態肯定是,l指向了第一個≥target的元素。
具體來說,l不可能指向后幾個≥target的元素,因為l只會每次l都在<target的情況下。向右移動一個元素,一旦l≥target,循環存在,r≥l,此時只會改變r的位置。
由于上面推論3,代碼還可增加一行優化成:
class Solution:def searchInsert(self, nums: List[int], target: int) -> int:l = 0r = len(nums)-1while(l <= r):mid = (l+r) // 2if(nums[mid] < target):l = mid + 1else:r = mid - 1if(l>=len(nums) or nums[l] >= target): return lreturn l
需要注意的是,以上代碼返回的索引可能會超出原有的數組邊界,在以后活用此方法時,應該注意到這個問題。