[Java] 이진 탐색

나무위키

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 10, 20, 30, 40, 50, 60};
        System.out.println(binarySearch(arr, 30));
        System.out.println(binarySearch2(arr, 30, 0, arr.length - 1));
        //자바 메소드
        System.out.println(Arrays.binarySearch(arr, 30));
        System.out.println(Arrays.binarySearch(arr, 11)); //-5
    }

    //반복문
    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);
        }
    }
}

자바의 이진 탐색 메소드 Arrays.binarySearch()를 사용하여 존재하지 않는 요소를 탐색할때 삽입되어야할 위치를 반환한다. e.g. 4번째 요소 뒤에 위치해야한다면 -5를 반환