[Java/알고리즘] 이진 탐색(Binary Search) 이해하기

1. 이진 탐색 (Binary Search)

이진 탐색은 대상 값을 찾을 때 까지, 범위를 절반씩 줄여가가는 알고리즘이다.

• 단점으로는 모든 데이터가 정렬되어 있어야 한다.
• 스무고개와 비슷하다.

이진 탐색의 과정 :

1. 배열의 가운데 요소를 선택한다.
2. 가운데 요소가 타겟 값과 같으면 탐색을 종료한다.
3. 만약 타겟값이 아니라면 가운데 요소를 타겟값과 비교한다.
   1. 타겟 값이 더 작으면 가운데 요소의 왼쪽 부분부터 탐색을 시작한다.
   2. 타겟 값이 더 크면 가운데 요소의 오른쪽 부분부터 탐색을 시작한다.
4. 이 과정을 반복하여 타겟 값을 찾거나 탐색 범위가 더 이상 없을 때 까지 계속한다.