[알고리즘] 이진탐색 (Binary Search)

이진 탐색이란 ?

검색 범위를 줄여나가며 특정 데이터를 검색하는 알고리즘 

 

정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를  찾는 알고리즘이다.

리스트 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.

 

1. 배열의 중간 값을 가져온다.

2. 중간 값과 검색 값을 비교한다.

- 중간 값이 검색 값과 같으면 종료 

- 중간 값이 검색 값보다 크다면 중간 값 기준 오른쪽구간을 대상으로 탐색

- 중간 값이 검색 값보다 작으면 중간 값 기준 왼쪽구간을 대상으로 탐색