二分查找 ||蟒蛇 ||数据结构和算法

百变鹏仔 5天前 #Python

文章标签蟒蛇

二分查找

二分搜索是一种反复将搜索空间一分为二的算法。这种搜索技术遵循分而治之的策略。每次迭代中搜索空间总是减少一半。导致时间复杂度为 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)

文章推荐

二分查找 ||蟒蛇 ||数据结构和算法

二分查找

代码

代码

代码

2020年适用于Linux程序员的10个最佳Python集成开发环境

获取字典中的第一个和最后一个元素的Python程序

在Python中漂亮地打印XML

Python日志基础 - 简易指南

如何在Python中创建静态类数据和静态类方法？