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

: 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘

실생활 예시

1. 간단한 것으로 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 위치에 따라 앞쪽을 찾거나 뒤쪽을 찾고, 찾을 때까지 그걸 반복하는 걸 생각하면 쉽다.

2. 술자리에서의 up/down 게임의 효율적 전략과 완벽히 일치한다.→ 나무위키 왈

숫자 범위를 지정해놓고, 한 사람이 어떤 숫자를 마음속으로 생각하면, 맞히는 사람이 한가지 숫자를 던졌을 때 생각해 둔 숫자가 그 숫자보다 큰지, 혹은 작은지 알려주면서 점점 범위를 줄여 정답을 유추하는 놀이이다. 이 놀이에서 가장 빠르고 효율적으로 정답을 찾아내는 방법이 무엇일까? 바로 범위의 중간값에 위치한 수를 던지는 것이다. 범위가 1부터 100이라고 한다면 처음엔 50, 그보다 크다고 하면 75, 그보다 작다고 하면 62... 이런 식이다. 이 역시 이진 탐색의 한 가지 좋은 예시로서, 자연수는 기본적으로 개념 자체가 순서대로 정렬되어있는 개념이기 때문에 이것을 써먹을 수 있는 것이다.

HOW?

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

이진 탐색 알고리즘은 리스트의 중간 값과 비교하여 검색값을 찾는다.

중간 값을 찾아야 하기 때문에 반드시 정렬된 배열에서만 사용할 수 있다.(뒤쪽에 자세한 설명 있)

이진 탐색의 동작 방식

1. 배열의 중간 값을 가져옵니다.
2. 중간 값과 검색 값을 비교합니다.
   1. 중간 값이 검색 값과 같다면 종료합니다. (mid = key)
   2. 중간 값보다 검색 값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색합니다. (mid < key)
   3. 중간 값보다 검색 값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색합니다. (mid > key)
3. 값을 찾거나 간격이 비어있을 때까지 반복합니다.

검색 예