[알고리즘]-이진 탐색

이진(이분) 탐색 (Binary Search)

이진탐색

이진 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 방법

해당 알고리즘은 검색범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다.

아래의 이미지는 이진 탐색을 가장 잘 나타내는 이미지다.

이미지를 보았을 때 찾을려고 하는 값은 37이다.
37을 찾기위해서 아래의 방법에서는 1에서 부터 하나씩 확인을 하고 넘어가는 단순한 방법을 이용하였다.

만약 아래의 방법에서 특정한 값이 앞 부분에 위치했으면 빨리 찾기는 하겠지만, $37$이라는 값을 찾기위해서 11번을 확인을 하였다.

반대러 이진 탐색을 진행한 위 방법에서는 3번 확인을 통해 특정 값을 빠르게 찾았다.

• 적용 조건

  이지탐색 적용 조건으로 가장 중요한 부분이 해당 배열이 정렬되어 있어야 적용이 가능하다.
  정렬이 되지 않은 배열에서는 이진탐색을 직접 적용할 수 없다.

  정렬이 되어 있어야 하는 이유로는 이진 탐색은 배열의 중간 지점을 시작으로 찾고자 하는 값과 중간 지점의 값을 비교를 시작으로 검색 범위를 반으로 줄여나가는 방식이기 때문에 알고리즘의 효율성을 위해서는 해당 배열이 정렬이 되어 있어야 한다.

• 동작 원리

  1. 탐색하고자 하는 배열에 찾고자 하는 값을 정의를 한다. 이때 해당 배열은 정렬이 되어 있어야 한다.

  2. 탐색 범위 low가 high보다 작거나 같은 동안 탐색을 진행한다.

  3. 현재의 탐색 범위의 중간 인덱스를 계산한다. 중간 인덱스(mid)는 low와 high의 평균 값으로 정한다. (일반적으로 내림 값을 이용)

  4. 배열의 mid 인덱스에 해당하는 값과 target을 비교를 진행한다.
     만약 mid == target 일 경우, 이 경우는 탐색을 성공했기 때문에 mid인덱스를 반환

     mid > target 일 경우, target이 mid보다 왼쪽에 위치하기 때문에 다음 탐색에서 high값을 mid - 1의 값으로 지정

     mid < target 일 경우, target이 mid보다 오른쪽에 위치하기 때문에 다음 탐색에서 low 값을 mid + 1의 값으로 지정
     

  5. 앞의 과정을 반복하여 mid == target일 경우 해당 탐색은 성공했기 때문에 mid의 인덱스 값을 반환하면 끝이다.

• 장점과 단점

  장점

  • 이진탐색은 $O(log$ $n)$의 시간 복잡도를 갖는다. 따라서 대규모 데이터에서도 빠르게 특정한 값을 찾을 수 있다는 장점이 있다.
  • 이진탐색은 선형 탐색과 비교했을 때 매우 큰 데이터 셋에서의 탐색 속도가 월등하게 빠르다.

  단점

  • 데이터가 정렬되어 있어야 한다. 데이터의 정렬에 추가적으로 시간이 소요가 된다.
  • 동적인 데이터 집합에서는 부적격하다. 이는 배열 중간에 새로운 값이 추가/삭제되는 경우, 이진탐색 트리와 같은 다른 자료 구조를 고려하는 것이 좋겠다.

• 구현

  • 반복문을 이용

    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                return mid;  // Target found
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        int[] myArray = {1, 3, 5, 7, 9, 11};
        int target = 5;
        int result = binarySearch(myArray, target);
        
        System.out.println("Index of " + target + " is: " + result); // Output: Index of 5 is: 2
    }  

  • 재귀 함수를 이용

      public static int binarySearch(int[] arr, int low, int high, int target) {
        if (high >= low) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] == target) {
                return mid; // Target found
            } else if (arr[mid] < target) {
                return binarySearch(arr, mid + 1, high, target);
            } else {
                return binarySearch(arr, low, mid - 1, target
            }
        }
        return -1; // Target not found
    }
    
    public static void main(String[] args) {
        int[] myArray = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int result = binarySearch(myArray, 0, myArray.length - 1, target);
        
        System.out.println("Index of " + target + " is: " + result); // Output: Index of 7 is: 3
    }

  이진 탐색을 구현하는데 있어 가장 기본적인 방법으로는 반복문과 재귀 함수를 이용하는 방법이 있다.