線性搜尋與二元搜尋

Data Structures and Algorithms in 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)$

線性搜尋與二元搜尋的圖形比較。

一起來練習吧！

Data Structures and Algorithms in Python