이진 탐색(Binary Search)

• 이진탐색 혹은 이분탐색이라고도 한다.
• 이미 정렬되어 있는 자료구조에서 특정 값을 찾을 때, 탐색 범위를 절반씩 나누면서 해당 값을 찾는다.
• 순차 탐색에 비해 빠르다는 장점을 가지고 있다.

시간복잡도

• 전체 탐색: O(N)
• 이진 탐색: O(logN)
  
  • 예시) 배열의 길이가 8인 경우 (n = 8):
    • 첫 번째 비교에서 배열을 절반으로 나눔 (4개 요소 남음)
    • 두 번째 비교에서 다시 절반으로 나눔 (2개 요소 남음)
    • 세 번째 비교에서 또 절반으로 나눔 (1개 요소 남음)
    • 따라서, 총 3번의 비교가 필요함. ( log⁡2(8)=3 )

처리순서

1. 정렬이 되어 있거나 정렬을 함
2. left, right로 mid값을 결정
3. mid와 구하고자 하는 값(target)을 비교
4. 구할 값이 mid보다 큰 경우, left = mid + 1
5. 구할 값이 mid보다 낮은 경우, right = mid - 1
6. right < left가 될 때까지 반복
7. mid값과 target값이 같으면 종료

관련 문제도 풀어봤는데 다시 풀어봐야 할 것 같다.