이진 탐색 Binary Search + Java 코드 구현

이진 탐색 (Binary Search)

개요

• 정렬된 데이터를 대상으로만 사용할 수 있다 ★
• 반복적 접근: 배열의 중간 위치(값 기준X)를 기준으로 탐색을 진행하고, 목표값(검색 타겟)이 중간 값보다 작거나 큰지에 따라 탐색 범위를 줄임.

개념

투 포인터 방식을 사용함 ★

1. 초기 설정: 시작 인덱스(left)와 끝 인덱스(right)를 설정합니다. 
   처음에는 left는 배열의 첫 번째 인덱스, right는 마지막 인덱스입니다.
2. 중간 값 계산: 중간 인덱스(mid)를 계산합니다. 이는 mid = (left + right) / 2로 구할 수 있습니다.
3. 비교:
   - 만약 arr[mid]가 찾고자 하는 값(target)과 같다면, 해당 인덱스를 반환합니다.
   - 만약 arr[mid]가 target보다 크다면, 탐색 범위를 왼쪽 절반으로 줄입니다 (right = mid - 1).
   - 만약 arr[mid]가 target보다 작다면, 탐색 범위를 오른쪽 절반으로 줄입니다 (left = mid + 1).
4. 반복: 위 과정을 left가 right보다 작거나 같은 동안 반복합니다.
5. 결과: target을 찾지 못한 경우 -1을 반환합니다.

시간복잡도

• 최악의 경우 : O(log n) - 배열의 크기가 n일 때, 탐색 범위가 매번 반으로 줄어들기 때문에 로그 시간 복잡도를 가짐.
• 최선의 경우 : O(1) - 중간 값이 바로 찾고자 하는 값인 경우
• 평균의 경우 : O(log n)

---

코드 구현

static int binarySearch(int[] arr, int target) {
    // 투 포인터
    int left = 0;
    int right = arr.length - 1;

    // 종료 조건: 포인터끼리 만날 때까지 (모두 탐색함)
    while (left <= right) {
        int mid = (left + right) / 2;       // 중간 위치 설정
        if (arr[mid] == target) return mid; // 반환 조건: mid가 target이 될 때 반환함

        // mid의 위치를 기준으로 포인터를 옮김
        if (target < arr[mid]) {
            right = mid -1;
        } else if (target > arr[mid]) {
            left = mid + 1;
        }
    }

    // 디폴트 반환: 모든 데이터를 탐색했음에도 배열 내에 target이 존재하지 않음
    return -1;
}

 

테스트 코드

// Test Run
public static void main(String[] args) {
    int[] arr = {1,3,5,9,10,11,14,29};
    System.out.println(binarySearch(arr, 3));
}