二分查找實(shí)現(xiàn)
def bsearch(self, nums, target):
low, high = 0, len(nums)
while low <= high:
middle = low + ((high - low) >> 1)
if nums[middle] == target:
return True
elif nums[middle] > target:
high = middle - 1
else:
low = middle + 1
return False
遞歸實(shí)現(xiàn)
def binaySearch(self, nums, target):
return self.bsearchInternally(nums, 0, len(nums) - 1, target)
def bsearchInternally(self, nums,low, high, target):
if low > high: return False
mid = low + ((high - low) >> 1)
if nums[mid] == target:
return True
elif nums[mid] > target:
high = mid - 1
else:
low += 1
return self.bsearchInternally(nums, low, high, target)
1. 循環(huán)退出條件
low <= high
2. mid的取值
mid = (low + high) // 2, 當(dāng)low 和 high比較大時候, 兩者之和可能會溢出, 改進(jìn)寫法 mid = low + (high - low) // 2, 優(yōu)化寫法mid = low + ((high - mid)>>1)
3.low 和 high 更新
low = mid + 1, high = mid - 1
二分查找應(yīng)用場景
1. 二分查找依賴順序表結(jié)構(gòu), 數(shù)組
2. 針對有序數(shù)據(jù)
3. 數(shù)據(jù)太小不適合二分查找
4. 數(shù)據(jù)太大也不適合
二分查找變形
- 查找第一個值等于給定值的元素
def bsearch(self, nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = low + ((high - low) >> 1)
if nums[mid] > target: high = mid - 1
elif nums[mid] < target: low = mid + 1
else:
if mid == 0 or nums[mid - 1] != target: return mid
high = mid - 1
return -1
- 查找最后一個值等于給頂元素
def bsearchLast(self, nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = low + ((high - low) >> 1)
if nums[mid] > target:
high = mid - 1
elif nums[mid] < target:
low = mid + 1
else:
if mid == len(nums) - 1 or nums[mid + 1] != target: return mid
low = mid + 1
return -1
- 查找第一個大于等于給定值的元素
def bsearchFirst(self, nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = low + ((high - low) >> 1)
if nums[mid] >= target:
if mid == 0 or nums[mid - 1] < target: return mid
else:
high = mid - 1
else:
low = mid + 1
return -1
- 查找最后一個小于等于給定值的元素
def bsearchLastSmallOrEqual(self, nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = low + ((high - low) >> 1)
if nums[mid] > target:
high = mid - 1
else:
if mid == len(nums) - 1 or nums[mid + 1] > target: return mid
low = mid - 1
return -1
