アルゴリズム入門　その４

※個人のアウトプットのために記述しています。

二分探索法

二分探索法は、配列からデータを探索するアルゴリズム。前回（アルゴリズム入門 その絵３）とは異なる。
この探索法は配列を真ん中あたりデータが整列（ソート）されているときだけ適用できる！

上記の『データが整列』された状態とは？　→　データを昇順（小→大）または降順（大→小）に並べた状態のこと

demo code

algorithm_2.rb

def binary_search(list, target)
  low = 0
  high = list.length - 1

  while low <= high
    # 中央値
    mid = (low + high)/2
    if list[mid] == target
      return mid
    elsif  list[mid] > target
      high = mid - 1
    else
      low = mid + 1
    end
  end
  return nil
end

# 下記の配列条件で３を探したい場合
list = [1,3,5,7,9]
p binary_search(list, 3)

参考資料・記事

• アルゴリズム図鑑
  

• たのしいRuby
  https://tanoshiiruby.github.io/6/

• 現役シリコンバレーエンジニアが教えるアルゴリズム・データ構造・コーディングテスト入門
  https://www.udemy.com/course/python-algo/?referralCode=92EDE0DC1C6C63F7F25E

• アルゴリズム、データ構造の基本(鳥羽眞嘉さん)
  https://zenn.dev/masahiro_toba/books/436c018f5cd4e2