Binary Search
时间复杂度:
T(n) = T(n/2) + O(1) = O(logn)通过O(1)的时间,把规模为n的问题变为n/2
思考:通过O(n)的时间,把规模为n的问题变为n/2?
通用模板:
class Solution:
# @param nums: The integer array
# @param target: Target number to find
# @return the first position of target in nums, position start from 0
def binarySearch(self, nums, target):
if len(nums) == 0:
return -1
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) / 2
if nums[mid] < target:
start = mid
else:
end = mid
if nums[start] == target:
return start
if nums[end] == target:
return end
return -1
Last updated
Was this helpful?