Python中如何实现快速查找算法

2023-04-16 00:00:00 算法如何实现快速查找

Python中实现快速查找算法可以使用二分查找法。该算法只适用于已排序的列表或数组。其原理是将待查找的值与中间值进行比较，如果待查找的值小于中间值，则在列表或数组的左半部分继续查找；如果待查找的值大于中间值，则在列表或数组的右半部分继续查找；如果待查找的值与中间值相等，则返回该中间值的索引。

以下是Python实现二分查找法的代码演示：

def binary_search(arr, x):
    """
    在已排序数组arr中查找x
    返回x在arr中的索引，如果不存在则返回-1
    """
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid

    return -1

使用字符串进行演示时，可以将字符串拆分为字符列表，然后按照字符的ASCII码值进行排序，以便使用二分查找法进行查找。

def string_search(string, x):
    """
    在已排序字符串string中查找x
    返回x在string中的索引，如果不存在则返回-1
    """
    arr = list(string)
    arr.sort()

    return binary_search(arr, x)

下面是一个使用字符串进行演示的例子：

string = "pidancode.com"
x = "p"
print(string_search(string, x))  # 输出0

x = "z"
print(string_search(string, x))  # 输出-1

此处以字符串“pidancode.com”为例，先将其拆分为字符列表["p", "i", "d", "a", "n", "c", "o", "d", ".", "c", "o", "m"]，再按照ASCII码值升序排序得到[".", "a", "c", "c", "d", "d", "e", "i", "m", "n", "o", "o", "p"]，然后使用二分查找法查找字符"p"，返回结果为索引0。如果查找的字符为"z"，则返回结果为-1，表示该字符串中不存在字符"z"。

相关文章