알고리즘 - Binary Search

this-is-spear·2023년 2월 12일

알고리즘

알고리즘도 재밌어

목록 보기

2/2

Binary Search은 무엇인지

Binary Search

Binary Search 알고리즘은 정렬된 배열에서 원소를 찾을 때까지 반복적으로 배열의 반씩 나누어 탐색 범위를 줄이는 방식이며, 탐색 속도는 $O(log n)$ 입니다.
Linear 검색의 시간복잡도인 $O(n)$ 보다 빠르고 사용하는 메모리도 비슷하기 때문에 Binary Search는 효율적인 탐색 방법입니다.

이진 탐색의 탐색 시간을 시간 복잡도로 증명

일부 $m >= 1$ 에 대해 $T(m) = O(log m)$ 이라 가정할 때, 아래와 같이 표현할 수 있습니다.

T(2m) = T(m) + 1 = O(logm) + 1 = O(log2m)

즉, 모든 $n >= 1$ 에 대해 $T(n) = O(log n)$ 이라는 결론을 내릴 수 있습니다.

Binary Search 활용

Binary Search를 이용해 해결할 수 있는 문제는 많습니다. 공통적으로 크기가 다른 여러 개의 선택지에서 적합한 원소를 찾는 경향있습니다.

원소가 존재하는지 판단 가능
일치하는 원소 개수 판단 가능
범위 검색 가능

Binary Search 구현

중간 원소와 찾는 원소의 크기를 비교해나가며 탐색 범위를 줄입니다.
start와 end의 원소를 변경할 때, 무한 루프가 발생하지 않도록 주의해야 합니다.

class BinarySearch {

  int[] arr;

  public BinarySearch(int[] arr) {
    Arrays.sort(arr);
    this.arr = arr;
  }

  public boolean binarySearch(int target) {
    int start = 0;
    int end = arr.length - 1;

    while (start <= end) {
      int mid = (start + end) / 2;

      if (arr[mid] == target) {
        return true;
      }

      if (target < arr[mid]) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }

    return false;
  }
}

Binary Search 구현 활용 - 일치하는 원소 개수 판단

scanLeftElementEqualsOrOver() 메서드는 찾는 원소와 같거나 큰 원소 중 배열 가장 왼쪽에 있는 원소를 반환합니다.
scanRightElementEqualsOrBelow() 메서드는 찾는 원소와 같거나 작은 원소 중 배열 가장 오른쪽에 있는 원소를 반환합니다.
두 원소의 인덱스 값을 빼면 일치하는 원소의 개수가 몇개인지 판단이 가능합니다.

class BinarySearchForRangeScan {

    int[] arr;

    public BinarySearchForRangeScan(int[] arr) {
      Arrays.sort(arr);
      this.arr = Arrays.copyOf(arr, arr.length + 1);
    }

    private int scanRightElementEqualsOrBelow(int target) {
      int start = 0;
      int end = arr.length;

      while (start < end) {
        int mid = (start + end) / 2;
        if (arr[mid] > target) {
          end = mid;
        } else {
          start = mid + 1;
        }
      }
      return start;
    }

    private int scanLeftElementEqualsOrOver(int target) {
      int start = 0;
      int end = arr.length;

      while (start < end) {
        int mid = (start + end) / 2;
        if (arr[mid] >= target) {
          end = mid;
        } else {
          start = mid + 1;
        }
      }
      return start;
    }
  }