python 折半查找

Python折半查找，也称为二分查找，是一种在有序数组中查找特定元素的算法。它要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列（升序或者降序）。时间复杂度为O(log2n)，每次循环都会舍弃一半的查找空间，空间复杂度为O(1)，使用一个整型变量mid记录中间的值。具体编码可以参考以下代码：

def binSearch(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            high = mid - 1
        elif nums[mid] < target:
            low = mid + 1

a = binSearch([1,3,5,7,8,9],3)
print(a)

相关问题

python折半查找1024

要在Python中实现折半查找，你可以使用下面的代码：

a = sorted(eval(input()))  # 将输入转化为列表，并排序
b = int(input())

def find(ls, item):
    low = 0
    high = len(ls)
    while low < high:
        mid = int((low + high) / 2)
        temp = ls[mid]
        if temp == item:
            return mid
        elif temp > item:
            high = mid - 1
        else:
            low = mid + 1
    return False

if find(a, b) is False:
    print('not find')
else:
    print('{} {}'.format(b, find(a, b)))

这段代码使用了折半查找的思想来查找给定的值。首先，它将输入转化为一个列表并进行排序。然后，它定义了一个`find`函数，该函数接受一个列表和要查找的项作为参数。在`find`函数中，它使用了两个指针`low`和`high`来表示查找范围的起始位置和结束位置。然后，它使用一个循环来将查找范围分成两半，直到找到满足条件的记录或者查找失败。在每一次循环中，它计算中间位置的索引`mid`，获取中间位置的值`temp`，并将其与要查找的项进行比较。如果它们相等，就返回中间位置的索引。如果中间位置的值大于要查找的项，就将查找范围缩小为前一半。如果中间位置的值小于要查找的项，就将查找范围缩小为后一半。如果循环结束时仍然没有找到满足条件的记录，就返回`False`表示查找失败。最后，根据查找结果进行输出。

因此，如果你想在给定的排序列表中使用折半查找来查找1024，你可以将列表输入给代码，并输入1024作为要查找的项。然后，代码将返回结果，如果找到了满足条件的记录，它会输出该记录的索引和值，否则会输出'not find'表示查找失败。

使用python完成折半查找

以下是使用Python完成折半查找的示例代码：

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

在这个函数中，输入参数`arr`是一个已排序的列表，`target`是我们要查找的目标值。函数通过不断折半缩小查找范围，直到找到目标值或者确定目标值不在列表中为止。如果找到了目标值，函数返回该值在列表中的下标，否则返回-1。