이분 탐색/이진 탐색 (Binary Search) - Java 코드

이분(=이진)탐색을 알아보자.

 

이분탐색은 정렬되어 있는 Resource 에서 특정 Resource 를 찾고자 할 때 사용된다. 매우 빠른 탐색 알고리즘으로 탐색 시간은 아래와 같다.

 

---

예제

ex) [4, 1, 5, 2, 3, 8, 7, 9, 6] 배열에 숫자 1 이 존재하는지 탐색

---

Java 코드는 다음과 같다.

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        binarySearch(1, new int[] {4, 1, 5, 2, 3, 8, 7, 9, 6});
    }


    /**
     * @param num 탐색해야하는 수
     * @param arr 배열 리스트
     */
    private static boolean binarySearch(int num, int[] arr) {
    	Arrays.sort(arr);
    
        int mid = 0;
        int left = 0;
        int right = arr.length - 1;

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

            if (num == arr[mid])
                return true;
            else if (num < arr[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }

        return false;
    }
}