알고리즘 - 이진 탐색

이진 탐색 (Binary Search) 란?

정렬된 배열에서 특정 값을 찾는 효율적인 방법으로, 시간복잡도는 O(log n)

public class Main {
    // 반복문 구조
    public static int binarySearch(int arr[], int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (target == arr[mid]) {
                return mid;
            } else if (target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
    
    // 재귀 호출 구조
    public static int binarySearch2(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;

        if (target == arr[mid]) {
            return mid;
        } else if (target < arr[mid]) {
            return binarySearch2(arr,  target, left, mid - 1);
        } else {
            return binarySearch2(arr, target, mid + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};

        System.out.println("Index: " + binarySearch(arr, 30));
        System.out.println();

        System.out.println("Index: " + binarySearch2(arr, 30, 0, arr.length - 1));
    }
}

반복문 구조

public static in binarySearch(int arr[], int target) {
	int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
    	int mid = (left + right) / 2;
    
    	if (target == arr[mid]) {
    		return mid;
    	} else if (target < arr[mid]) {
    		right = mid - 1;
    	} else {
    		left = mid + 1;
    	}
    }
    return -1;
}

1. left 와 right 포인터를 배열의 처음과 끝으로 초기화
2. while 반복문을 이용하여 left가 right보다 작거나 같은 동안 반복
3. mid 포인터를 배열의 중간 위치로 계산
4. target 값이 arr[mid] 와 같다면 mid를 반환
5. target 값이 arr[mid] 보다 작다면, right를 mid - 1 로 이동
6. target 값이 arr[mid] 보다 크다면, left를 mid + 1로 이동
7. 값을 찾지 못하면 -1을 반환

재귀 호출 구조

public static int binarySearch2(int arr[], int target, int left, int right)
	if (left > rigth) {
    	return -1;
    }
    int mid = (left + right) / 2;
    
    if (target == arr[mid]) {
    	return mid;
    } else if (target < arr[mid]) {
    	return binarySearch2(arr, target, left, mid - 1);
    } else {
    	return binarySearch2(arr, target, mid + 1, right);
    }
}

1. left 가 right보다 크다면 -1을 반환하여 값이 배열에 없음을 나타냄
2. mid 포인터를 배열의 중간 위치로 계산
3. target 값이 arr[mid]와 같다면, mid를 반환
4. target 값이 arr[mid]보다 작다면, 배열의 왼쪽 부분을 대상으로 재귀 호출
5. target 값이 arr[mid]보다 크다면, 배열의 오른쪽 부분을 대상으로 재귀 호출

요약

반복문 구조 : 루프를 통해 배열의 중간값과 비교하며 탐색 범위를 줄여나감
재귀 호출 구조 : 현재 배열의 중간값과 비교하여 탐색 범위를 줄여나가는 방식으로 재귀 호출을 통해 해결

자바 기본 binarySearch

import java.util.Arrays;

public class Main2 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};

        System.out.println("== 데이터가 있는 경우 ==");
        System.out.println(Arrays.binarySearch(arr, 1));
        System.out.println(Arrays.binarySearch(arr, 10));
        System.out.println(Arrays.binarySearch(arr, 30));

        System.out.println("== 데이터가 없는 경우 ==");
        System.out.println(Arrays.binarySearch(arr, 3));
        System.out.println(Arrays.binarySearch(arr, 11));
        System.out.println(Arrays.binarySearch(arr, 35));
    }
}

데이터가 있는 경우

-Arrays.binarySearch(arr, 1) 은 0을 반환 (1의 인덱스)
-Arrays.binarySearch(arr, 10) 은 3을 반환 (10의 인덱스)
-Arrays.binarySearch(arr, 30) 은 5을 반환 (30의 인덱스)

데이터가 없는 경우

찾고자 하는 값이 배열에 없는 경우 Arrays.binarySearch는 음수를 반환. 반환값은 -(삽입 점 + 1).
삽입 점은 해당 값을 배열에 삽입해야 할 위치를 의미

-Arrays.binarySearch(arr, 3) 은 -3을 반환. 3이 배열에 없다면 삽입점은 2번 인덱스에 삽입되어야 하기 때문에 반환값은 -(2 + 1) = -3
-Arrays.binarySearch(arr, 11) 은 -5을 반환. 11이 배열에 없다면 삽입점은 4번 인덱스에 삽입되어야 하기 때문에 반환값은 -(4 + 1) = -5
-Arrays.binarySearch(arr, 35) 은 -7을 반환. 35가 배열에 없다면 삽입점은 6번 인덱스에 삽입되어야 하기 때문에 반환값은 -(6 + 1) = -7