線形探索と二分探索

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は中央の位置の1つ前を指し、さらに変数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

二分探索

ソートされているリストにのみ適用可能

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という変数は中央の位置に1を加えた位置を指し、lastという変数は最後の位置を指し、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

二分探索

ソートされているリストにのみ適用可能

数値が順序付きで並んだリストの模式図。中央のポインターが移動し、最初と最後の間にある要素を指している。最初と中央の位置の間にある要素は緑色で表示されている。

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

二分探索

ソートされているリストにのみ適用可能

数値が順序付きで並んだリストの模式図。中央のポインターが移動し、最初と最後の間にある要素を指している。最初と中央の位置の間にある要素は緑色で表示されている。中央の点である要素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

二分探索

ソートされているリストにのみ適用可能

数値が順序付きで並んだリストの模式図。最後のポインターは移動され、最初のポインターと同じ数値を指している。

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 ???
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と比較される。

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)$

線形探索と二分探索の図解。

練習しましょう！

Pythonで学ぶデータ構造とアルゴリズム