二分查找
二分搜索是一种反复将搜索空间一分为二的算法。这种搜索技术遵循分而治之的策略。每次迭代中搜索空间总是减少一半。导致时间复杂度为 o(log(n)),其中 n 是元素数量。
条件:数组应该是排序的,但它们也可以应用于单调函数,我们需要找到单调递增或单调递减。
当我们需要以对数时间缩小搜索空间时,它就有效。
我们使用两个指针,左指针和右指针。取左右的平均值来找到中间元素。
现在,我们根据条件检查应该将左右指针移动到哪里。
解决一个问题主要需要三个步骤:
- 预处理: 如果输入未排序,则对输入进行排序。
- 二分查找:使用两个指针并找到中间部分来划分搜索空间,然后相应地选择正确的一半。
- 后处理:确定输出。
二分搜索算法的优点 – 对于大数据,二分搜索比线性搜索更快,因为它每次将数组切成两半,而不是逐一检查每个元素。这使得它更快、更高效。
限制:二分查找仅适用于已排序的数组,因此对于小型未排序数组效率不高,因为排序需要额外的时间。对于小型内存搜索,它的效果也不如线性搜索。
应用: 用于在排序数组中搜索元素,时间复杂度为 o(log(n)),也可用于查找数组中的最小或最大元素。
基本二分查找代码 –
代码
def binarysearch(nums, target): if len(nums) == 0: return -1 left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 # end condition: left > right return -1
33。在旋转排序数组中搜索
给定可能旋转后的数组 nums 和整数目标,如果目标在 nums 中,则返回目标索引,如果不在 nums 中,则返回 -1。
您必须编写一个运行时间复杂度为 o(log n) 的算法。
示例1:
输入:nums = [4,5,6,7,0,1,2],目标 = 0
输出:4
示例2:
输入:nums = [4,5,6,7,0,1,2],目标 = 3
输出:-1
示例3:
输入:nums = [1],目标 = 0
输出:-1
代码
class solution: def search(self, nums: list[int], target: int) -> int: left = 0 right = len(nums)-1 while left <= right: mid = (left + right)//2 print(f'left is {left},right is {right} and mid is {mid}') if nums[mid]==target: return mid if nums[mid] >= nums[left]: # if nums[mid]< target and target >= nums[left]: if nums[left] <= target < nums[mid]: right = mid -1 else: left = mid +1 else: # if nums[mid] < target and target <= nums[right]: if nums[mid] < target <= nums[right]: left = mid +1 else: right = mid - 1 return -1
- 使用左右两个指针,迭代直到它们重叠。
- 找到中间元素。
- 由于数组已排序但已旋转,所以我们不能简单地将左侧或右侧的元素与中间的元素进行比较。
- 首先,通过比较中指针与左指针或右指针来确定左部分或右部分排序。
- 根据这个结论,相应地调整指针。
时间复杂度 – o(log(n)),因为搜索空间在每次迭代中被分成两半。
空间复杂度 – o(1)
单调递增
162。找到峰值元素
峰值元素是严格大于其邻居的元素。
给定一个 0 索引的整数数组 nums,找到一个峰值元素,并返回其索引。如果数组包含多个峰值,则返回任意峰值的索引。
您可能会想象 nums[-1] = nums[n] = -∞。换句话说,一个元素总是被认为严格大于数组外部的邻居。
您必须编写一个在 o(log n) 时间内运行的算法。
示例1:
输入:nums = [1,2,3,1]
输出:2
说明:3 是峰值元素,您的函数应返回索引号 2。
示例2:
输入:nums = [1,2,1,3,5,6,4]
输出:5
说明:您的函数可以返回索引号 1(峰值元素为 2)或索引号 5(峰值元素为 6)。
代码
class Solution: def findPeakElement(self, nums: List[int]) -> int: left = 0 right = len(nums) -1 while left <= right: mid = (left+right)//2 if mid >0 and nums[mid] < nums[mid-1]: right = mid -1 elif mid < len(nums)-1 and nums[mid] < nums[mid+1]: left = mid+1 else: return mid
- 在此类问题中,我们需要通过比较中间的左侧或右侧元素来检查峰值。
- 这有助于确定图表趋势是向上还是向下。
- 要找到最大值,请搜索向上的斜率并探索正确的子空间。
- 要找到最小值,请搜索左侧子空间
时间复杂度 – o(log(n)),因为搜索空间在每次迭代中被分成两半。
空间复杂度 – o(1)