이진탐색을 알아보자!

이진 탐색은 정렬된 배열 또는 리스트에서 사용하는 탐색 방법 중 하나이다.

아이디어

 

중간 값을 이용하여 찾고자 하는 항목이 왼쪽에 있는 지 오른쪽에 있는 지를 알아내어 탐색의 범위를 반으로 줄이자

사용할 수 있는 경우

• 고정되고 정렬된 데이터 탐색의 경우 적합

public class algo1_1 {

    static int[] nums = {1,4,7,9,10,11,13,17,20,23};

    public static void main(String args[]) throws IOException {

        BufferedReader br1 = new BufferedReader(new InputStreamReader(System.in));
        int find = Integer.parseInt(br1.readLine());

        System.out.println(binarySearch(nums,find));

    }

    public static int binarySearch(int[] nums, int find){

        int head = 0;
        int tail = nums.length - 1;
        int ans;

        while(true){
            int mid = (head + tail)/2;
            ans = nums[mid];
            if(head > tail){
                break;
            }
            if(ans == find){
                break;
            } else if (ans < find) {
                head = mid + 1;
            }else {
                tail = mid - 1;
            }
        }
        return ans;

    }

}

시간복잡도

탐색횟수 : k

데이터의 갯수 : N

비교 범위

0	N
1	N/2
2	N/4
…	…
k	N/2^k

탐색 범위가 1이 될때가 탐색이 완료된 순간이다.

따라서, 1 = N/2^k

 

k = logN 의 시간복잡도를 갖는다.