이진탐색 알고리즘

이진탐색은 정렬된 상태에서 사용 가능합니다. 리스트에 원하는 데이터가 있으면 데이터의 위치를 반환하고 없으면 null을 반환합니다.

Ex

  1. 1~100 사이에 숫자를 하나를 생각합니다.
  2. 범위를 절반을 기준으로 줄여나갑니다. (100 - 50 - 25 - 13 - 7 - 4 - 2 - 1)
  3. 최대 7단계

처음부터 순차적으로 탐색하는 단순 탐색은 위와 같은 범위를 가질 때 최대 99번을 반복해야 찾을 수 있기에 효율적이지 못합니다.

log2N

n개의 데이터를 가진 리스트에 이진 탐색을 사용할 시 최대 log2N번의 횟수가 발생합니다.

log란 거듭 제곱의 반댓말로 log2 8일때 2 * 2 * 2 = 3번의 횟수를 의미합니다.

실행 시간

선형시간

계산복잡도 이론상 에서 입력의 길이 n에 대해 특정 알고리즘의 실행시간이 선형의 특징을 가지는 것을 말합니다. 예를 들어 100의 길이를 가진 원소를 단순탐색으로 자료를 확인한다면 100번의 횟수를 확인해야 하고 이때 걸리는 시간을 선형시간이라 말합니다.

로그시간

정렬된 리스트를 이진탐색 사용시 원소의 log2N번의 횟수로 자료를 찾을 수 있습니다. log28 -> 3회, log232 -> 5회, log21024 -> 10회 이진탐색의 경우 로그시간으로 실행됩니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static Integer binarySearch(int[] list, int target) {

        int low = 0;
        int high = list.length - 1;

        while(low <= high) {
            int mid = (low + high) / 2;
            int guess = list[mid];
            
            if(guess == target) {
                return mid;
            }
            
            //찾고자 하는 값이 절반 값보다 크면 mid 값에 다음 인덱스를 low로
            //반대로 찾고자 하는 값이 절반 값보다 작으면 mid 위치의 바로 전 인덱스를 high로
            if(guess < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return null;
    }

Reference