이진탐색

1. 이진탐색(Binary Search)

- 이진 탐색은 정렬된 배열에서 특정 값을 찾는 매우 빠른 탐색 알고리즘

- 이름처럼 데이터를 '이분(binary)', 즉, 절반씩 나눠가며 탐색

ex) 업다운(UP-DOWN) 게임 (*업다운(UP-DOWN) : 1~100까지의 숫자를 정해서 그 숫자를 맞추는 게임, UP하고 DOWN으로만 알려준다)

 

 

2. 기본 동작 방식

1. 시작점, 끝점, 중간점 설정: 배열의 맨 처음 인덱스를 low, 맨 마지막 인덱스를 high. mid = (low + high) / 2로 설정
2. 중간값과 비교: 배열[mid] 값이 내가 찾으려는 값(target)과 같은지 확인한다
   • 찾았다면?: 탐색 종료! 
   • 찾는 값보다 중간값이 크다면?: 찾는 값은 무조건 왼쪽에 있으니, 탐색 범위를 왼쪽 절반으로 좁힌다. (high = mid - 1)
   • 찾는 값보다 중간값이 작다면?: 찾는 값은 무조건 오른쪽에 있으니, 탐색 범위를 오른쪽 절반으로 좁힌다. (low = mid + 1)
3. 반복: 찾을 때까지 1, 2번 과정을 계속 반복해. 만약 low가 high보다 커지면 배열 안에 찾는 값이 없다는 뜻

 

3. 특징

• 빠른 속도: 탐색을 한 번 할 때마다 검색 범위가 절반씩 줄어듬. 그래서 시간 복잡도가 O(logn)으로 매우 빨라. 데이터가 100만 개여도 약 20번만 비교하면 값을 찾을 수 있어.
• 필수조건 : 반드시 데이터가 정렬되어 있어야 함. 
• 데이터 접근: 배열의 어떤 위치든 바로 접근(Random Access)할 수 있어야 하므로, 배열(Array)에 가장 적합