[알고리즘 구현] 이진탐색 (BinarySearch)

이진탐색(Binary Search)

: 정렬 된 데이터에서 사용할 수 있으며, 가운데를 기준으로 큰지 작은지 비교하여 매번 탐색할 양의 반을 줄여나가는 탐색방법.

public class MyBinarySearch {
    // 반복문 구조
    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(arr[mid]==target) {
                return mid;
            } else if(arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

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

public static void main(String[] args) {
    int[] arr = {1, 2, 4, 6, 10, 15, 20, 30, 50, 100};
    System.out.println(Arrays.toString(arr));
    System.out.println("bns1] key: 15 -> Idx: " + binarySearch(arr, 15));
    System.out.println("bns1] key: 3 -> Idx: " + binarySearch(arr, 3));
    System.out.println("bns2] key: 15 -> Idx: " + binarySearch2(arr, 15));
    System.out.println("bns2] key: 3 -> Idx: " + binarySearch2(arr, 3));
    System.out.println("== Java 기본제공 이진탐색 ==");
    System.out.println("bns] key: 15 -> Idx: " + Arrays.binarySearch(arr, 15));
    System.out.println("bns] key: 3 -> Idx: " + Arrays.binarySearch(arr, 3));
}
/*
[1, 2, 4, 6, 10, 15, 20, 30, 50, 100]
bns1] key: 15 -> Idx: 5
bns1] key: 3 -> Idx: -1
bns2] key: 15 -> Idx: 5
bns2] key: 3 -> Idx: -1
== Java 기본제공 이진탐색 ==
bns] key: 15 -> Idx: 5
bns] key: 3 -> Idx: -3
*/

*Java 기본제공 이진탐색 - 값이 없을 경우 그 값이 만약 있다면 어디에 위치해야하는지 인덱스를 리턴함. (부호를 바꾸고 -1을 한 곳. 즉, -3이라면 배열의 2 위치에 해당 키 값이 있으면 된다는 뜻)

---

마지막 수정일시: 2022-06-22 00:00