6. 이진 탐색 알고리즘

• 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 
• 이진 탐색:  정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 
  • 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 

 주의할 점은 해당 알고리즘은 정렬되어있는 경우에 사용할 수 있다는 것이다. 

만약 정렬이 되어있지 않은 경우에는 시간 복잡도가 '정렬 시간 복잡도' * '이분 탐색 시간 복잡도'라고 생각해야 한다. 

이진 탐색의 시간 복잡도 

• 단계마다 탐색 범위를 2로 나누는 것과 동일하다. (연산 횟수는 log(2)N에 비례한다.  '()'는 밑을 의미)
• 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장한다.

public class BinarySearch {

    private static int search(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) { // while문 대신 재귀적으로 동작시킬 수도 있지만 while 방식이 좋다. 
            int mid = (start + end) / 2;
            if (arr[mid] == target) {
                return mid;
            }

            if (arr[mid] > target) {
                end = mid - 1;
                continue;
            }

            start = mid + 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 7, 10, 15, 19, 21, 23};
        int target = 21;
        int resultPosition = BinarySearch.search(arr, target);
        System.out.println("결과 index: " + resultPosition);
    }
}

이미 Java 라이브러리에는 binarySearch 함수가 존재한다! 이를 활용해도 좋다!

추가적으로 만약 라이브러리로 없는 target으로 함수를 실행시키면, target으로 지정한 값보다 바로 다음으로 큰 값의 index를 음의 값으로 가진채로 리턴한다.

Java 라이브러리가 제공하는 binarySearch의 알고리즘을 까보면 아래와 같다. 

>>> 가 뭐였지하고 가물가물했는데... 비트 연산자 였다.   참고자료

파라메트릭 서치(Parametric Search) 

• 파라메트릭 서치란 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법이다. 
  • 예시: 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 
• 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다. 

주어진 문제가 큰 탐색 범위를 가진다면... 가장 먼저 이진 탐색을 떠올려야 한다.