이진 탐색 (Binary Search)

특징

• 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법
  • 찾고자 하는 값과 데이터 중앙에 있는 값을 비교
  • 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색
  • 찾고자 하는 값이 더 크면 데이터 오른족 부분에서 이진 탐색
• O(logN)

탐색 과정

• 30을 찾는 과정
  

소스코드

// 알고리즘 - 이진 탐색

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

        while (left <= right) { //left가 right보다 커지면 원하는 값이 배열안에 없다는 의미
            int mid = (left + right) / 2;

            if (target == arr[mid]) {   // 해당 데이터 찾음
                return mid;
            } else if (target < arr[mid]) { //찾는 값이 arr[mid]보다 작으면 mid 왼쪽편 탐색
                right = mid - 1;
            } else {    //찾는 값이 arr[mid]보다 크면 mid 오른쪽편 탐색
                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));
    }
}

JAVA 기본 라이브러리 활용

• '해당 데이터가 있을 경우의 위치'란 순서대로 정렬되어 있는 값에서 그 값이 있을 위치

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("== 데이터가 없는 경우 ==");
        // -1 반환이 아닌 '-(해당 데이터가 있을 경우의 위치) - 1'을 반환
        System.out.println(Arrays.binarySearch(arr, 3));
        System.out.println(Arrays.binarySearch(arr, 11));
        System.out.println(Arrays.binarySearch(arr, 35));
    }
}