線形探索と二分探索

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−1、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 は middle+1、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で学ぶデータ構造とアルゴリズム