线性搜索与二分搜索

Python 中的数据结构与算法

Miriam Antona

Software engineer

搜索算法

搜索是一项基础操作
- 多种方式
在集合中查找元素的算法：
- 线性搜索
- 二分搜索

线性搜索

逐个遍历元素

无序数字列表的示意图。

找到元素
- 算法停止
- 返回结果
未找到元素
- 算法继续

线性搜索

def linear_search(unordered_list, search_value):

  for index in range(len(unordered_list)):

    if unordered_list[index] == search_value:

      return True

  return False

print(linear_search([15,2,21,3,12,7,8], 8))

True

print(linear_search([15,2,21,3,12,7,8], 800))

False

线性搜索 - 复杂度

复杂度：$O(n)$

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。

15 在哪？

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。有一个名为 first 的变量指向列表的第一个位置。

15 在哪？

def binary_search(ordered_list, search_value):
  first = 0

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。有一个变量 first 指向列表第一个位置，另一个变量 last 指向最后一个位置。

15 在哪？

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1


  while first <= last:

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。有变量 first 指向第一个位置，last 指向最后一个位置，middle 指向中间位置。

15 在哪？

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。变量 first 指向第一个位置，变量 last 指向最后一个位置，变量 middle 指向中间位置。数字 12 位于中间并用黄色标出。

15 在哪？
将 search_value 与列表中间的元素比较

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

    if search_value == ordered_list[middle]:

      return True

    elif search_value < ordered_list[middle]:

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。变量 first 指向第一个位置，变量 last 指向中间位置减一，变量 middle 指向中间位置。first 与 middle 之间的元素用绿色标出。

15 在哪？
将 search_value 与列表中间的元素比较

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。变量 first 指向第一个位置，变量 last 指向最后一个位置，变量 middle 指向中间位置。数字 12 位于中间并用黄色标出。

15 在哪？
将 search_value 与列表中间的元素比较

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。变量 first 指向中间位置加一，变量 last 指向最后一个位置，变量 middle 指向中间位置。first 与 middle 之间的元素用绿色标出。

15 在哪？
将 search_value 与列表中间的元素比较

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。middle 指针移动，指向 first 和 last 之间的元素。first 与 middle 之间的元素用绿色标出。

15 在哪？
将 search_value 与列表中间的元素比较

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。middle 指针移动，指向 first 和 last 之间的元素。first 与 middle 之间的元素用绿色标出。middle 指向的元素 17 将与数字 15 比较。

15 在哪？
将 search_value 与列表中间的元素比较

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。last 指针移动，与 first 指向同一个数字。

15 在哪？
将 search_value 与列表中间的元素比较

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。middle 指针移动，与 first 和 last 指向同一个数字。

15 在哪？
将 search_value 与列表中间的元素比较

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。first、last 和 middle 指针都指向同一个数字 15，将与数字 15 比较。

15 在哪？
将 search_value 与列表中间的元素比较

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

二分搜索

仅适用于有序列表

包含有序数字的列表示意图。数字 15 被圈出。

15 在哪？
将 search_value 与列表中间的元素比较

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

  return False

二分搜索 - 复杂度

复杂度：$O(\log{}n)$

线性搜索与二分搜索的图示对比。

Passons à la pratique !

Python 中的数据结构与算法