Python中如何实现快速查找算法
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"。
相关文章