이진탐색 (Binary Search)

오늘은 이진탐색 (Binary Search) 알고리즘 에 대해 정리해 두려고 한다.

 

이진탐색 이란?

이진 탐색은 정렬된 배열의 가운데 값과 키값을 비교하고 비교 대상을 좌우로 줄여가면서 비교를 되풀이 하는 방법이다. 

 

아래 그림을 보면 간단하게 이해 되지 않을까 싶다.

 

먼저 key 값은 6 이고, 배열은 {1,4,6,8,11,13,15} 라고 가정했다.

 

1. 먼저 8 (mid) 과 6 (key) 을 비교 했을 때, key 값보다 mid 값이 크기때문에  8(mid) 값보다 작은 1,4,6 대상으로 범위를 줄인다.

2. 다음은 4 (mid) 와 6 (key) 을 비교 했을 때, key 값보다 mid 값이 작기 때문에 4(mid) 값보다 큰 6 을 대상으로 범위를 줄인다.

3. 다음은 6(mid) 와 6 (mid)를 비교했을 때 , key 값과 같기 때문에 6 이 위치한 index 값인 2를 리턴한다.

 

소스코드

public class BinarySearch {
    public static void main(String[] args) {
        BinarySearch b = new BinarySearch();
        int[] arr = {1,4,6,8,11,13,15};
        System.out.println(b.binarySearch(6, arr));

    }
    public int binarySearch(int key, int arr[]) {
        int mid;
        int l = 0;
        int r = arr.length-1;

        while(r>=l) { // 배열에 탐색할 숫자기 있는지 체크
            mid= (r+l)/2; // 중간 값 설정
            if(key == arr[mid]) return mid; // 키값과 일치하면 index 리턴

            if(key < arr[mid]) // 키값이 중간값보다 작으면
                r = mid-1;  // 중간값 앞부분만 검색할 수있도록 right 값 새롭게 설정
            else // 키값이 중간값보다 크면
                l = mid+1; // 중간값 뒷부분만 검색할 수 있또록 left 값 새롭게 설정
        }

        return -1;
    }
}

 

끝.