이진탐색이란?

배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법

이진탐색의 효율성

1억 개 목록을 선형탐색할 때, 1억 번을 연산해야 한다. 이진탐색으로 찾는다면, 27번 안에 찾을 수 있다.

import math

math.log2(100000000) # 26.575424759098897

이진탐색을 위해서는 정렬되어 있어야 한다.