[알고리즘 탐색] 이진 탐색(Binary Search)

  이진 탐색(Binary Search)이란 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법입니다. 데이터가 정렬되지 않은 상태라면 진행할 수 없습니다.

  찾고자 하는 값과 데이터 중앙에 있는 값을 비교합니다. 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서, 더 크면 데이터 오른쪽 부분에서 이진 탐색을 진행합니다. 알고리즘 시간 복잡도는 O(log n)입니다.

  단점으로는 데이터의 삽입과 삭제가 빈번하면 정렬을 유지하기 위해 시간이 오래 걸린다는 점입니다. 1회의 삽입이나 삭제 연산 수행 시 최악의 경우 O(n) 시간이 소요됩니다.

 

이미지 출처: 위키백과, 이진 검색 알고리즘 항목

 

  이진 탐색 구현 코드(반복문)

public static int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (target == array[mid]) {
            return mid;
        } else if (target < array[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

  매개 변수로 배열 array와 정수형 target을 받는 binarySearch 메소드를 생성합니다.

  변수 left와 right를 생성합니다. 각각 배열에서 제일 좌측의 위치와 제일 우측의 위치를 할당합니다.

  while문에서 좌측의 위치보다 우측의 위치가 크거나 같을 때 반복합니다.

  변수 mid를 생성합니다. 좌측 값과 우측 값을 더한 값을 2로 나눈 값을 할당합니다. 중앙 인덱스를 구한 것입니다.

  if문에서 target, 즉 찾고자 하는 값이 array의 mid번째 원소와 같다면 mid를 반환합니다.

  else if에서 target이 array의 mid번째 원소보다 크다면 right에 mid에서 1을 뺸 값을 할당합니다. 이는 우측의 위치를 재조정하는 것입니다. mid보다 작은 값 중에서 찾아야 하기 때문입니다.

  앞선 조건에 해당하지 않는다면, 즉 target이 array의 mid번째 원소보다 작다면 left에 mid에서 1을 더한 값을 할당합니다. 이는 좌측의 위치를 재조정하는 것입니다. mid보다 큰 값 중에서 찾아야 하기 때문입니다.

  만약 앞선 탐색을 진행한 뒤 array에 target에 해당하는 값이 없다면 -1을 반환하여 찾는 값이 존재하지 않음을 알립니다.