[알고리즘] 이진탐색

  이진탐색 알고리즘은 정렬이 되어있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

 

  먼저 배열의 중간값을 찾고하자는 값과 비교한다. 그리고 중간값이 찾고하자는 값보다 크다면 배열의 왼쪽, 작다면 배열의 오른쪽 부분으로 탐색 범위를 제한하여 다시 탐색한다. 탐색 단계가 진행될 때마다 탐색 범위는 반씩 줄어든다.

  시간 복잡도는 빅오표기법에 따라 O(logN)과 같다.
  이진탐색은 선형탐색에 비해 속도가 빠르지만 정렬이 되어 있는 데이터에만 적용할 수 있다는 단점이 있다.

 

예시

{1, 12, 38, 41, 60}

위와 같은 배열에서 41을 찾는다고 하자.
배열의 길이는 5이고 중간값은 3이다.
배열의 인덱스는 0부터 시작하므로 2번 인덱스의 값은 38이다.

38은 41보다 작기때문에 찾고자하는 값은 배열의 가운데 기준, 오른쪽에 있다는 걸 알 수 있다.
탐색 범위를 중간 인덱스 오른쪽으로 좁힌다.

 

 

{1, 12, 38, 41, 60}

두번째 탐색의 범위는 배열의 3-4번 인덱스로 줄어들었다.
이번에 배열의 중간 인덱스는 3.5다. 소수점 이하를 버리고 3번 인덱스를 찾고자하는 값과 비교한다.
배열의 3번 인덱스인 41은 찾고자하는 값과 같다. 탐색이 종료된다.

 

 

 

만약 찾고자하는 값이 배열에 없는 값인 43이었다면 어땠을까?

{1, 12, 38, 41, 60}

41은 43보다 작기때문에 탐색 범위는 3번 인덱스의 오른편으로 좁혀진다.

탐색 범위의 시작 값은 3 + 1인 4번, 끝 값은 배열의 마지막 인덱스인 4번이 된다.
4번 인덱스의 값은 60이다. 60은 찾고자하는 값인 43보다 크기 때문에 탐색 범위 끝은 배열의 왼쪽으로 좁혀지게 된다. 그러면 탐색범위의 시작값은 그대로 4번 인덱스, 끝 값은 4 - 1인 3번이 된다.
이렇게 되면 시작 인덱스 4번, 끝 인덱스는 3이 되므로 탐색이 종료된다.

  찾는 값이 배열에 존재하지 않을 때는 보통 -1을 돌려준다.

 

 

 

코드로 구현하면 아래와 같다.

 

코드

public class BinarySearch {

    static int search(int[] numbers, int target) { //반복문을 이용한 구현

        int firstIdx = 0; // 탐색범위의 시작 인덱스는 최초 0부터 시작한다
        int lastIdx = numbers.length -1; // 탐색범위의 마지막 인덱스

        //시작 인덱스가 끝 인덱스보다 큰 경우 탐색이 종료된다
        while(firstIdx <= lastIdx) {

            // 배열의 중간 인덱스를 찾는다
            int middleIdx = (firstIdx + lastIdx) / 2; 

            // 중간값이 찾는 값보다 큰 경우 탐색 범위의 마지막 인덱스를 중간값 -1로 잡는다
            if(numbers[middleIdx] > target) { 
                lastIdx =  middleIdx - 1;
            // 중간값이 찾는 값보다 작은 경우 탐색 범위의 시작 인덱스를 중간값 +1로 잡는다
            }else if(numbers[middleIdx] < target) { 
                firstIdx = middleIdx + 1;
            }else {
                return middleIdx;
            }
        }
        return -1; // 값을 찾지 못하고 반복문을 벗어났을 경우 -1을 반환해준다
    }

    //재귀호출을 이용한 구현
    static int searchRecursion(int[] numbers, int firstIdx, int lastIdx, int target) { 
        if(firstIdx > lastIdx) {
            return -1;
        }

        int middleIdx = (firstIdx + lastIdx) / 2;

        if(numbers[middleIdx] > target) {
            return searchRecursion(numbers, firstIdx, middleIdx -1, target);
        }else if(numbers[middleIdx] < target) {
            return searchRecursion(numbers, middleIdx + 1, lastIdx, target);
        }else {
            return middleIdx;
        }

    }

    public static void main(String[] args) {
        int[] numbers = {1, 10, 25, 42, 60, 112};
        int target = 25;

        int idx = search(numbers, target);
        System.out.println(idx);

        int idx2 = searchRecursion(numbers, 0, numbers.length-1, target);
        System.out.println(idx2);

    }
}