Binary Search

< 개념 >

---

< 자체구현 >

// 알고리즘 - 이진탐색

package binarySearch;

public class BinarySearch {
    // 반복문 구조
    public static int binarySearch1(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 (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            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: " + binarySearch1(arr, 30));
        System.out.println();

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

 

< 내장 >

// 내장
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("===데이터가 없는 경우===");
// 반환값 : -(있었다면 어느 인덱스에 존재 + 1)
System.out.println(Arrays.binarySearch(arr, 3));            // -3
System.out.println(Arrays.binarySearch(arr, 11));           // -5
System.out.println(Arrays.binarySearch(arr, 100));   

 

 

- 내장을 직접 구현

// 이진탐색 추가 구현
/*
    target값이 arr 내에 있으면 해당 인덱스 반환
    없으면 해당 값이 이을 경우의 위치에 -1을 곱하고 1을 뺀 값을 반환

    예시)
    입력 : 1,2,5,10,20,30,40,50,60
    target : 30
    출력 : 5

    target : 3
    출력 : -3
*/

package binarySearch;

public class Practice1 {
    public static int solution(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 if (target > arr[mid]) {
                left = mid + 1;
            }
        }


        return -left - 1;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,5,10,20,30,40,50,60};
        System.out.println(solution(arr, 30));      //5
        System.out.println(solution(arr, 3));       //-3
        System.out.println(solution(arr, 11));      //-5
        System.out.println(solution(arr, 35));      //-7
    }
}

 

 

 

 

! If !, 인덱스값이 너무 크다면 mid 구하는데 overflow 발생할 것임.

그럴 때는,

// arr가 너무 클 때, idx의 값이 커질 때(overflow 방지)
// int mid = left + (right - left) / 2;