[JAVA/알고리즘] 이진 탐색(Binary Search)

이진탐색 (Binary Search)은 정렬되어 있는 배열에서 데이터를 검색할 때, 탐색 범위를 절반씩 줄여가며 찾아가는 알고리즘이다.

    public static int binarySearch(int[] arr, int target) {
        int answer = 0;
        int lt = 0; // 왼쪽끝 lt
        int rt = arr.length - 1; // 오른쪽끝 rt

        Arrays.sort(arr); // 정렬된 배열
        while (lt <= rt) {
            int mid = (lt + rt) / 2;
            if (arr[mid] == target) { // 찾으면 return
                answer = mid;
                break;
            }
            if (arr[mid] > target) // 찾는값이 mid보다 작으면 rt값 조정
                rt = mid - 1;
            else lt = mid + 1; // mid보다 크면 lt값 조정
        }
        return answer;
    }

 

시간복잡도 

탐색 대상을 절반씩 계속해서 줄여나가기 때문에, 시간복잡도는O(log n)이다.