【LeetCode练习|算法通关手册:Python版】03. 数组篇_二分查找【未完待续】
2021/11/23 22:10:01
本文主要是介绍【LeetCode练习|算法通关手册:Python版】03. 数组篇_二分查找【未完待续】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2021.11.23-2021.11.25 Datawhale 11月学习内容;学习地址:https://algo.itcharge.cn/
文章目录
- 1. 二分查找
- 2. 二分查找题目
- LeetCode 704. 二分查找
- LeetCode 374. 猜数字大小
- LeetCode 35. 搜索插入位置
- LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
1. 二分查找
基本算法思想:是一种在有序数组
中查找某一特定元素的搜索算法。先确定待查找元素所在的区间范围,在逐步缩小范围,直到找到元素或找不到该元素为止。
- 每次查找时从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;
- 如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。
- 如果在某一步骤数组为空,则代表找不到。
事例: 假设原始序列为array=[3, 12, 24, 31, 46, 48, 52, 66, 69, 79, 82],目标元素target=52。
- 开始时,low=0,high=10,mid=(low + high) / 2 = 5。
- 此时,比目标值小,说明在右侧。
low=5+1=6
,high=10,mid=(low + high) / 2 = 8。
- 此时,比目标值大,说明在左侧 low=6,
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
2. 二分查找题目
LeetCode 704. 二分查找
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
LeetCode 374. 猜数字大小
https://leetcode-cn.com/problems/guess-number-higher-or-lower/
- 这道题多少感觉有点问题,以下是答案,如果有看懂的给我讲一下
int guess(int num)
来获取猜测结果
class Solution: def guessNumber(self, n: int) -> int: left = 1 right = n while left <= right: mid = (right + left) // 2 ans = guess(mid) if ans == 1: left = mid + 1 elif ans == -1: right = mid - 1 else: return mid return 0
LeetCode 35. 搜索插入位置
https://leetcode-cn.com/problems/search-insert-position/
-
为了效率满足,用了二叉查找,思路没有一点变化,和原理无异
-
唯一不同就是这里要输出插入位置
-
当找到一样值的时候,这个值得位置就是插入的位置
-
如果搜索到最后没找到这个值,也就是结束条件
left > right
,一定是应该插入到left
这个位置,所以return left
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: n = len(nums) left = 0 right = n - 1 ans = n while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return left
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
这道题如果按正常思路,从小到大找呗,然后找到输出就行。但是本题要求$O(logn)$
思想:
- 用二叉查找发 先找到这个值
- 然后向两边找,直到出现不同
class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: left = 0 right = len(nums) - 1 ans = [-1, -1] while left <= right: mid = (left + right) // 2 if nums[mid] == target: nums.append(0.1) ans[0] = ans[1] = mid while (ans[0]-1>=0) and (nums[ans[0]-1] == target) : ans[0] -= 1 while (nums[ans[1]] == target) and ((ans[1]+1) <= len(nums)-1): ans[1] += 1 ans[1]= ans[1] -1 return ans if nums[mid] < target: left = mid + 1 else: right = mid - 1 return ans
- 是在二分法相等的条件下做往两端延伸看是否与
target
相等。我遇到的问题就是边界的判断 - 当最左端是目标时,如【2,2,3】target =2,因为
nums[-1]
是有值的(list最后一个),但我们要防止它套圈,所以加了条件ans[0]-1 >= 0
- 另一个是最右端处理,因为+1 要超出nums长度的,所以我在末尾加了一个不可能出现的数
nums.append(0.1)
,使得循环不超界 - 最后,我们尝试一下特殊的数组,比如【】,【1】,【2,2】是否满足
这篇关于【LeetCode练习|算法通关手册:Python版】03. 数组篇_二分查找【未完待续】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-27使用python 将ETH账户的资产打散
- 2024-09-26Python编程基础
- 2024-09-2610 种方法写出更好的 Python 代码
- 2024-09-25Python编程基础详解
- 2024-09-25Python编程入门教程
- 2024-09-25从零开始使用Python构建LLaMA 3
- 2024-09-23Python中理解和使用树形结构的简单教程
- 2024-09-23Python 编程基础入门
- 2024-09-18初探Python股票自动化交易:入门指南
- 2024-09-18Python量化入门:轻松掌握量化分析基础与实战