搜索

在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
# 二分法搜索返回True或False
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
# 二分法搜索返回index
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
# 二分法递归搜索，返回True或False
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
# 二分法递归搜索，返回index
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)