搜索
在Python中,有一个非常简单的方法来判别特定项是否在列表中。我们使用in这个运算符。但为了说明这些搜索算法的工作原理以及它们相互比较时的优劣之分,我们还是自己实现这些算法。
无序列表的顺序搜索
1 2 3 4 5 6 7 8 9
| def sequentialSearch(alist, item): pos = 0 found = False while pos < len(alist) and not found: if alist[pos] == item: found = True else: pos += 1 return found
|
有序列表的顺序搜索
1 2 3 4 5 6 7 8 9 10 11 12
| def orderedSequentialSearch(alist, item): pos = 0 found = False stop = False while pos < len(alist) and not found and not stop: if alist[pos] == item: found = True elif alist[pos] > item: stop = True else: pos += 1 return found
|
二分法搜索
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| def binarySearch(alist, item): head = 0 tail = len(alist) - 1 found = False while head <= tail and not found: mid = (head + tail)//2 if alist[mid] == item: found = True elif alist[mid] < item: head = mid + 1 else: tail = mid - 1 return found
|
1 2 3 4 5 6 7 8 9 10 11 12 13
| def binarySearch2(alist, item): head = 0 tail = len(alist) - 1 while head <= tail: mid = (head + tail)//2 if alist[mid] == item: return mid elif alist[mid] < item: head = mid + 1 else: tail = mid - 1 return "The item '{}' is not found!".format(item)
|
1 2 3 4 5 6 7 8 9 10 11 12
| def binarySearch3(alist, item): if len(alist) == 0: return "The item '{}' is not found!".format(item) else: mid = len(alist)//2 if alist[mid] == item: return True elif alist[mid] < item: return binarySearch3(alist[mid+1:], item) else: return binarySearch3(alist[:mid], item)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| def binarySearch3(alist, item, head, tail): ''' 因为返回值是index,所以每次递归传回的列表必须是原列表, 这样才能保证index是在原列表中的index,而不是每次递归 缩小的列表的index ''' if head > tail: return "The item '{}' is not found!".format(item) else: mid = (head + tail)//2 if alist[mid] == item: return True elif alist[mid] < item: return binarySearch3(alist, item, mid+1, tail) else: return binarySearch3(alist, item, head, mid-1)
|