赞
踩
2021.11.23-2021.11.25
Datawhale 11月学习内容;学习地址:https://algo.itcharge.cn/
基本算法思想:是一种在有序数组
中查找某一特定元素的搜索算法。先确定待查找元素所在的区间范围,在逐步缩小范围,直到找到元素或找不到该元素为止。
事例: 假设原始序列为array=[3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82],目标元素target=52。
low=5+1=6
,high=10,mid=(low + high) / 2 = 8。high=mid-1=7
,mid=(low + high) / 2 = 6。low > high
)都没找到,那说明没有。代码:
def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 # 在区间 [left, right] 内查找 target while left <= right: # 取区间中间节点 mid = (left + right) // 2 # 如果找到目标值,则直接返回中心位置 if nums[mid] == target: return mid # 如果 nums[mid] 小于目标值,则在 [mid + 1, right] 中继续搜索 elif nums[mid] < target: left = mid + 1 # 如果 nums[mid] 大于目标值,则在 [left, mid - 1] 中继续搜索 else: right = mid - 1 # 未搜索到元素,返回 -1 return -1
方法二:排除法思想
class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 # 在区间 [left, right] 内查找 target while left < right: # 取区间中间节点 mid = left + (right - left + 1) // 2 # nums[mid] 大于目标值,排除掉不可能区间 [mid, right],在 [left, mid - 1] 中继续搜索 if nums[mid] > target: right = mid - 1 # nums[mid] 小于等于目标值,目标元素可能在 [mid, right] 中,在 [mid, right] 中继续搜索 else: left = mid # 判断区间剩余元素是否为目标元素,不是则返回 -1 return left if nums[left] == target else -1
if nums[mid] > target:
如果中间值大于目标值,那么一定在左半部分left = mid
left=right
结束(和while
条件相反的临界值)return left if nums[left] == target
就是相等的话返回坐标,其他情况返回-1
https://leetcode-cn.com/problems/binary-search/
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
ans = -1
while left <= right:
mid = (left+right)//2
if nums[mid] == target:
ans = mid
return ans
if nums[mid] < target:
left = mid+1
else:
right = mid-1
return ans
https://leetcode-cn.com/problems/guess-number-higher-or-lower/
int guess(int num)
来获取猜测结果class Solution:
def guessNumber
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。