이진 탐색(binary search)

탐색 문제중 선형 탐색(linear search)을 제외하면 가장 쉬운 탐색 방법

선형 탐색(linear search), 단순 탐색(simple search)

말은 그럴 듯 하지만, 하나씩 하나씩 찾는 방법

보통 배열의 첫번째 인덱스부터 순차적으로 찾아나갑니다.

탐색 시작 → 첫번째 인덱스 부터 대상 비교(반복) → 탐색 종료

찾는 대상이 앞에 있으면 있을 수록 속도는 빨라지고, 뒤에 있으면 있을 수록 속도는 O(n)에 가까워지게 됩니다.

데이터가 많으면 많을수록 속도는 그에 비례해 느려집니다.

장점

1. 데이터가 적을 때, 효율적일 수 있습니다.
2. 읽기 편합니다.
3. 이해하기 쉽습니다.
4. 정렬되어 있지 않아도 사용할 수 있습니다.

단점

1. 데이터가 조금만 많아져도 비효율적이게 됩니다.
2. 대상이 뒤에 있는 경우 느려지게됩니다.
3. 바보같습니다?

class LinearSearch {
    public int search(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

이진 탐색(binary search)

입력으로 정렬된 원소 리스트를 받습니다.

들어온 값의 절반을 체크합니다. → 크거나 작은지 판단합니다. 같다면 리턴합니다. → 해당하는 영역을 제외한 나머지 영역을 제거할 수 있습니다.

이진 탐색의 가장 큰 장점은 선택된 나머지 영역을 제외한 영역을 제거한다는 것입니다.

이는 선형탐색에 비해서 매우 빠른 속도로 동작할 수 있습니다.

속도는 O(logn)입니다. Big-O 표기법에서 모든 log는 log2를 뜻합니다.

만약 입력된 원소 리스트가 정렬이 되어있는지 안되어있는지 확실하지 않다면, 정렬을 해주어야 합니다.

실행 시간

선형 탐색의 시간을 선형 시간(linear time) 만큼 걸린다고 했을 때, 이진 탐색은 로그 시간(logarithmic time)으로 실행됩니다.

장점

1. 선형 탐색에 비해서 빠릅니다.

단점

1. 정렬이 되어있지 않다면 사용할 수 없습니다.
2. 앞의 대상이 요소라면 선형탐색이 빠릅니다. (탐색은 모든 경우를 고려해야합니다.)
3. 연결리스트에서는 사용하기 힘듭니다.(캐시, 메모리 지역성)

class BinarySearch {
    public int search(int[] arr, int target, int firstIndex, int lastIndex) {
        if (lastIndex < firstIndex) {
            return -1;
        }
      
        int middleIndex = (firstIndex + lastIndex) / 2;
        int middleValue = arr[middleIndex];
      
        if (target == middleValue) {
            return middleValue;
        } else if (target < middleValue) {
            return search(arr, target, firstIndex, middleIndex - 1);
        } else {
            return search(arr, target, middleIndex + 1, lastIndex);
        }
    }
}

class BinarySearch() {
    public int search(int[] arr, int target) {
        int firstIndex = 0;
        int lastIndex = arr.length - 1;
        
        while (firstIndex < lastIndex) {
            int middleIndex = (firstIndex + lastIndex) / 2;
            int middleValue = arr[middleIndex];
            
            if (target == middleValue) {
                return middleIndex;
            } else if (target < middleValue) {
                lastIndex = middleIndex - 1;
            } else {
                firstIndex = middleIndex + 1;
            }
        }
        
        return -1;
    }
}

재귀 없이도 이진 탐색이 가능합니다.

아이디어는 재귀와 동일합니다.

감사합니다.