1.3이진 탐색 알고리즘

선형 탐색을 먼저 알아본 이유는 선형 탐색에 비해 이진 탐색의 성능이 얼마나 좋은지 보여 주기 위해서였습니다.

이진 탐색 알고리즘을 요약하면 다음과 같습니다.

• 리스트의 모든 데이터는 정렬된 상태여야 한다.

• 첫 번째 인덱스를 start로 설정하고 마지막 인덱스를 end로 설정한다.

• 가운데 인덱스를 mid로 설정하고 mid 데이터와 target 데이터를 비교한다.

• target 데이터와 mid 데이터가 같다면 mid를 반환한다.

• target 데이터가 작다면 end를 mid - 1로 한다.

• target 데이터가 크면 start를 mid + 1로 한다.

• 데이터를 찾거나 start와 end가 교차하기 전까지 계속 진행한다.

• 데이터를 찾지 못했다면 None을 반환한다.

이진 탐색 알고리즘을 적용하려면 반드시 데이터가 정렬된 상태여야 합니다. 이미 정렬이 끝난 상태이므로 target이 mid의 데이터보다 작다는 것은 mid 이후 데이터는 모두 target보다 크다는 의미입니다. 즉, mid보다 인덱스가 작은 데이터만 비교하면 됩니다.