이진 탐색 Java 구현

이진탐색

이진 탐색이란 정렬되어 있는 배열에서 원하는 값을 찾아내는 탐색 방법중 하나이다. 이진탐색은 처음부터 찾는 것이 아니라 양 끝에서 부터 시작해 중간값과 찾으려는 값을 비교해서 배열을 2개로 나눠 찾으려는 값이 속한 배열에서 다시 이진탐색을 하는 방법이다. 처음부터 찾는 일반 탐색과 속도측면에서 매우 빠른 방법이다.

가장 주의해야 할 점은 이 탐색은 정렬된 배열에서 써야하는 것이다.

배열에서 찾으려는 값의 인덱스 번호를 리턴해주는 함수이다.

만약에 찾는 값이 없다면 -1을 리턴함

public int binary_search(int item, int[] numbers) {
        int left=0;
        int right = numbers.length-1;
        while(right >= left) {
            int mid = (left + right)/2;
            if(numbers[mid]==item) {
                return mid;
            }
            if(numbers[mid]>item) {
                right = mid-1;
            }else {
                left = mid+1;
            }
        }

        return -1;
    }