🌹 정리 by 장미(https://velog.io/@newbiekim/)

선형 자료구조의 대표적인 탐색 방법은 다음과 같이 세 가지가 있다.

1. Linear Serach(선형 탐색)
2. Binary Serach(이진 탐색)
3. Search by Hashing(해싱)

우리는 이번에 이진 탐색에 대해 알아볼 것이다.

이진 탐색 방법은 세 단계로 설명할 수 있다.

1. 값을 순서대로 나열한다.

   (여기서는 오름차순을 기준으로 설명하겠다.)

2. 가장 가운데 값을 고른다.

3. 고른 값보다 찾는 값이 더 크면 오른쪽으로, 작으면 왼쪽으로 이동해서 또 다시 가운데 것을 고른다. 값을 찾을 때까지 반복한다.

참고

가운데 값(중간 값)은 검색 범위 안에서의 (최소 인덱스 번호 + 최대 인덱스 번호) / 2 로 구한다. 이 때 소수점 이하는 버린다.

예: 검색 범위가 인덱스5 ~ 인덱스8일 경우 (5 + 8) / 2 = 6.5 이다. 소수점 이하는 버리므로 중간 값의 인덱스는 6이 된다.

그림으로 알아보자.