[알고리즘] 이진 탐색 방법

이진 탐색 ( Birnary Search )

 

🤔 단순 탐색과 문제점

사전에서 정지 라는 단어를 찾는다고 생각해보자. 보통의 사전은 자음과 모음 순으로 정렬되어 있다.

정렬되어 있다는 사실을 알았으니 우리는 ㄱ ~ ㅈ  까지 찾은 후 ㅏ ~ ㅓ 까지 찾아갈 것이다. 이렇게 앞에서부터 순서대로 찾아나가는 방법을 단순 탐색 이라고 부른다.

 

 

다만 이런 방식은 상당히 비효율 적일 수 있다. 만약 앞에서 32000번째 단어의 경우 찾기 위해 앞에서 부터 32000개의 단어를 확인 해보아야 한다.

 

 

💡 즉, M개의 정렬된 데이터를 찾기 위해 최대 M번 최소 1번 평균적으로 M/2번의 탐색 횟수가 필요하다.

 

 

👍 이진 탐색 ( Binary Search )

단순 탐색(Simple Search) 방식은 데이터의 개수가 늘어남에 따라 탐색 횟수도 늘어난다. 데이터 개수가 커질 수록 그 속도가 늦어진다는 의미다. 정렬된 데이터에 있어 해당 문제를 해결하는 더 빠른 방법이 있는데, 바로 이진 탐색 방법이다.

 

이진 탐색 설명을 위해 다시 사전에서 정지 라는 단어를 찾아보자. 자음 ㄱ~ㅎ 에서 ㅈ 은 그 중간인 ㅅ 보다 뒤쪽에 위치해있다. 그러면 앞에 ㄱ~ㅅ 을 버리자. 그리고 ㅇ~ㅎ 에 중간을 기준으로 다시 찾아 볼 수 있다. 이와 같이 정렬된 데이터의 중간을 기준으로 비교하는 과정을 반복해 나가며 탐색하는 방법을 이진 탐색( Binary Search ) 라고 한다.

이진 탐색은 탐색 횟수를 줄일 수 있다. 정렬된 10만개의 단어중 특정 단어를 찾기위해 아무리 많아도 log_{2}10000 번이면 충분하다.

 

 

💡 즉, M개의 정렬된 데이터를 찾기 위해 최대 log_{2} M번 최소 1번의 탐색 횟수가 필요하다. 이진탐색의 시간 복잡도는 O(log_{2} M) 이다.

 

 

이진탐색 평균 횟수 테스트

코드

이진 탐색 메서드

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

    while(low <= high) {
      mid = (low + high) / 2;
      if (arr[mid] == target){
        searchCount++;
        return searchCount;
      }
      else if (arr[mid] > target) {
        high = mid - 1;
        searchCount++;
      }
      else {
        low = mid + 1;
        searchCount++;
      }
    }
    return -1;
  }
}

Test

public class Test {

  public static final int NUMBERS = 100;
  public static final int MAX_VALUE = 100000000;
  static BinarySearch search = new BinarySearch();

  public static void main(String[] args) {
    long countTotal = 0L;
    for (int i = 0; i < MAX_VALUE; i++) {
      int target = (int) (Math.random() * NUMBERS + 1);
      int[] array = Arrays.stream(IntStream.range(1, NUMBERS).toArray()).toArray();
      int count = search.binarySearch(array, target);
      countTotal += count;
    }
    long avgCount = countTotal / MAX_VALUE;
    System.out.println(avgCount);
  }
  // 1_000 대해 100000000번 테스트 평균 5회
}

 

📝 1~100 까지 수를 100000000번 테스트 했을 때 평균 탐색 횟수 5회

 

참조

• Hello Coding 그림으로 개념을 이해하는 알고리즘