이분 탐색이란 ?

• 오름차순 또는 내림차순으로 정렬된 배열에서 특정 값을 찾는 알고리즘
• 이분 탐색은 탐색 범위를 절반씩 줄여 나가기 때문에 빠른 속도를 보장한다.
  • 단, 배열이 정렬되어 있어야 한다.

이분 탐색 과정

• 낮은 인덱스의 변수명 : low
  • 초기 값 : 0
• 높은 인덱스의 변수명 : high
  • 초기 값 : 배열의 길이 - 1
• 중간 인덱스의 변수명 : mid
  • 값 설정 식 : (low + high) / 2

1. 배열의 중간 값을 선택하여 찾고자 하는 값과 비교한다.

2. 만약, 중간 값이 찾고자 하는 값보다 크면 중간 값 왼쪽 부분에서 탐색을 진행하고

    값보다 작으면 중간 값 오른쪽 부분에서 탐색을 진행한다. 
   

• 중간 값이 찾고자 하는 값보다 클 경우 : 중간 값에 1을 빼서 왼쪽 절반을 탐색한다.

if (arr[mid] > key) {
	high = mid - 1;
}

• 중간 값이 찾고자 하는 값보다 작을 경우: 중간 값에 1을 더해서 오른쪽 절반을 탐색한다.

if (arr[mid] < key) {
	low = mid + 1;
}

3. 이 과정에서 찾고자 하는 값이 나올 때까지 반복한다.

이분 탐색의 성능

• 이분 탐색의 시간 복잡도는 O(logn)으로 다른 정렬에 비해 상대적으로 매우 빠르다.

이분 탐색을 선택해야 하는 판단 기준

1. 정답이 특정한 범위(연속된 수 구간) 안에 존재한다.
   • 길이, 시간, 비용, 개수 등 숫자 범위 안에서 정답을 찾는 문제
2. 그 범위 내에서 조건이 단 한 번만 가능/불가능으로 바뀔 때
   • ex. 길이를 늘릴 수록 가능한지/불가능한지가 한 번만 뒤바뀌는 경우
     • 길이 = 1 ~ 200 (가능) / 길이 = 201 ~ 802 (불가능)

이분 탐색의 문자열 탐색