이진 탐색

이진 탐색은 정렬된 배열 에서 원하는 값을 찾는 알고리즘이다.
이진 탐색은 탐색 범위를 1/2 씩 줄여가며 원하는 값을 탐색한다.

---

만약 아래와 같은 정렬된 배열이 있다고 가정하자.

int arr[] = {1,2,3,4,5,6,7,8,9,10};

이중에서 값이 '7' 인 인덱스를 찾으려면 어떻게해야하는가?
위 예제에서는 단순히 for문을 사용해서 arr[i] == 7 이 될 때까지 탐색하면 될 것이다.

하지만 만약 arr[i]의 길이가 10억이고, 우리가 찾아야 하는 숫자가 9억9999만9999 라면?

위와 같이 최악의 경우에는 연산하는데 약 10초의 시간, 굉장히 오랜 시간이 소요된다.

이 때 사용하는 방법이 바로 이진 탐색이다.

---

이진탐색은 인덱스를 사용하여 탐색을 진행한다.

int left = 0;
int right = arr.length - 1;

위와 같이 0번째 인덱스, arr의 마지막 인덱스를 각각 left, right 에 저장하고
이 두 개의 인덱스를 더하고 2를 나눈 값(mid) 을 찾으려는 값(target) 과 비교하는 방식 으로 진행한다.

이 상황에서 비교하는 경우는 총 3가지로 나뉜다.

• arr[mid] == target
  • 원하는 인덱스를 찾은 단계, mid에 7의 인덱스가 담겨있으므로 return 한다
• arr[mid] < target
  • mid 값이 찾으려는 값보다 작은 경우,
    mid의 값보다 작은 값들은 무조건 찾으려는 값보다 작으므로 left = mid + 1;
• arr[mid] > target
  • mid 값이 찾으려는 값보다 큰 경우,
    mid의 값보다 큰 값들은 무조건 찾으려는 값보다 크므로 right = mid - 1;

위 방식이 이진 탐색이다.

---

앞선 for문과 비교해보자.

for (int i = 0 ; i < arr.length ; i++)
   if (arr[i] = 7) {
      return i;
      break
   }
}

... arr[0] = 1
... arr[1] = 2
... ...
... arr[6] = 7 , 

위 코드상 7을 구하는데 까지 연산한 횟수는 총 7회이다.

이번엔 이진 탐색을 사용해보자.

int left = 0;
int right = arr.length - 1;

while (left <= right) {
	int mid = (left + right) / 2;
	if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        left = mid + 1;
    } else {
        right = mid - 1;
    } 
}

1. left = 0, right = 9
   mid = (0 + 9) / 2 , 4 
   arr[4] = 5, target 7보다 작음.
   then, left = mid + 1
   left = 5

2. left = 5, right = 9
   mid = (5 + 9) / 2 = 7
   arr[7] = 8, target 7보다 큼.
   then, right = mid - 1, 
   right = 6
   
3. left = 5, right = 6
   mid = (5 + 6) / 2 = 5
   arr[5] = 6, target 7보다 작음.
   then, left = mid + 1,
   left = 6
   
4. left = 6, right = 6
   mid = (6 + 6) / 2 = 6
   arr[6] = 7, target 7과 같음.
   then, return mid;
   정답을 찾음

위 와 같이 총 4번의 연산으로, 조금 복잡하지만 확실히 for문보다 더 빨리 7을 찾을 수 있다.

for문 7번의 연산,
이진탐색 4번의 연산이 비록 별로 차이가 없어 보일 수 있어도
만약 int arr[] 의 값이 위 예제처럼 10 이 아니라 10억이라면
비교 할 수 조차 없이 더 빨리 원하는 값을 찾을 수 있다.