[ 이분탐색(이진탐색) ]

“데이터를 검색하는 방법”

1. 개념 : 사과 속 씨 찾기

“반씩 쪼개고 찾자!”

문제 → 과정 → 리턴

• 문제 : 정렬된 리스트 S에 어떤 키 x가 존재하는가?
  • 전제 : 정렬된 리스트여야 한다. (정렬되어 있지 않은 경우는 ‘순차 탐색’)
• 과정 : 배열의 중앙값으로부터 작으면 왼쪽 이동 (오른쪽 버리기) / 크면 오른쪽 이동 (왼쪽 버리기)
• 리턴 : (존재 O) S에서 x의 위치 / (존재 X) 0 or 특정 값 리턴

2. 원리

• 필요한 데이터 : pl / pr / pc 인덱스

  → 배열의 첫 번째 / 배열의 마지막 / 배열의 중간((pl + pr) // 2)

1. a[pc]와 key 값을 비교한다.

2. a[pc] < key 이면 → pl = pc + 1 / pr = pr → 왼쪽 버리고 → **pc + 1 ~ pr**에서 찾기!

a[pc] > key 이면 → pl = pl / pr = pc - 1 → 오른쪽 버리고 → **pl ~ pc - 1**에서 찾기!

3. **a[pc] == key**가 될 때까지 2번 과정을 반복한다.

(혹은 검색범위가 더 이상 없는 경우, 끝난다.)

3. 대표적인 알고리즘

1) 반복문