Binary Search 이진 탐색 알고리즘

1. 이진탐색 정의

데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘

배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교

X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 재탐색

선택된 배열의 중간값을 다시 선택하고 위 과정을 반복하여 해당 값을 찾을 때까지 반복

 

2. 이진탐색 예시

ex) { 17, 28, 43, 67, 88, 92, 100 } , target = 43

2-1. arr = { 17, 28, 43, 67, 88, 92, 100 }, mid = 67

가운데에 위치한 67을 기준으로 43은 67보다 작다. 그렇다면 다음의 배열은 67보다 한칸 앞에 있는 것까지로 한다.

2-2. arr = { 17, 28, 43 }, mid = 28, mid = 28

43은 28보다 크므로, 배열의 왼쪽을 28보다 크게 한다.

2-3. arr = { 43 }, mid = 43

 

mid와 target의 값이 일치하므로 탐색을 종료한다.

 

만약 탐색을 했지만 해당하는 값이 아예 없다면 어떻게 될까?

40을 예로 들면 30 < mid = 43 이므로 좌측을 탐색해야 하지만 더이상 좌측이 없으므로, 해당하는 배열에 40이 없다고 판단하고 탐색을 종료한다.

 

이를 소스코드로 구현하면 다음과 같다.

 

3. 이진탐색 구현

3-1. 반복문

  public int BSearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
      mid = (low + high) / 2;

      if (arr[mid] == target)
        return mid;
      else if (arr[mid] > target)
        high = mid - 1;
      else
        low = mid + 1;
    }
    return -1;
  }

3-2. 재귀

 

  public int BSearch(int[] arr, int target, int low, int high) {
    if (low > high) return -1;
    
    int mid = (low + high) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] > target) return BSearch(arr, target, low, mid - 1);
    else return BSearch(arr, target, mid + 1, high);
  }

 

참고 : https://cjh5414.github.io/binary-search/