이진 검색

: 오름차순으로 정렬된 리스트에서 특정 값의 위치 찾기

프로세스

1. 배열의 중간에 있는 임의의 값(중앙값)을 선택
2. 찾으려는 값 x와 임의의 값을 비교
3. if x>임의의값 then, 임의의 값 기준 우측의 데이터들에서 다시 탐색
   else then, 임의의 값 기준 좌측의 데이터들에서 다시 탐색
4. 찾을 때까지 1~3 반복

예시

{17, 28, 43, 67, 88, 92, 100} x=43

1. (1회전) 배열의 중간 위치 값인 67 선택
2. 67>43 이므로, {17, 28, 43} 탐색
3. (2회전) 배열의 중간 위치 값인 28 선택
4. 27<43 이므로, {43} 탐색
5. (3회전) 배열의 중간 위치 값인 43 선택
6. 45==43 이므로, 탐색 종료

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} x=14
1. (1회전) 배열의 중간 위치 값인 8 선택
2. 8<14이므로, {9,10,11,12,13,14,15} 탐색
3. (2회전) 배열의 중간 위치 값인 12 선택
4. 12<14 이므로, {13,14,15} 탐색
5. (3회전) 배열의 중간 위치 값인 14 선택
6. 14==14 이므로, 탐색 종료