이진탐색(Binary Search)

 

정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법

- 찾고자 하는 값과 데이터 중앙에 있는 값을 비교

- 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색

- 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색

알고리즘 시간 복잡도 : O(logn)

 

이진 탐색의 구현

1. 탐색의 대상이 되는 자료들이 array[low] 에서부터 array[high]에 들어있다고 가정하자. (정렬되어 있어야 함)

즉 어떤 시점에서 탐색되어야 할 범위는 low에서 high 까지가 된다.

맨 처음 low에는 0번 인덱스의 값, high에는 n-1번 인덱스의 값이 들어갈 것이다.

 

2. low와 high값에 의거해  중간값mid 값은 (low + high) / 2이다.

즉, array[low] ~ array[high] 까지의 탐색은

array[low] ~ array[middle-1] +  array[middle+1] + array[high]까지의 탐색이 된다.

 

3. array[mid] 값과 구하고자 하는 key값을 비교한다.

3-1. key > mid :  구하고자 하는 값이 중간값보다 높다면 low를 mid +1로 만들어 줌 (왼쪽 반을 버림)

3-2. key < mid : 구하고자하는 값이 중간값 보다 낮다면 high를 mid-1로 만들어 줌 (오른쪽 반을 버림)

3-3. key == mid : 구하고자 하는 값을 찾음 중간값 리턴 

 

4. low > high가 될 때까지 1~3번을 반복하면서 구하고자 하는 값을 찾는다.

(이때까지 못 찾으면 탐색 실패 -1, false, error 등 return)

 

 

이진 탐색 과정

데이터가 우선 정렬된 상태여야 이진 탐색 진행 가능

찾고자 하는 데이터 : 30

반복문

// 반복문 구조
    public static int binarySearch(int arr[], int target) {
        int left = 0;
        int right = arr.length -1;

        while (left <= right){
            int mid = (left + right) / 2; // mid를 중앙으로 설정 해줌
        if(target == arr[mid]) return mid; // 찾고자 하는 target이 mid 면 return
        else if (target < arr[mid]) { // target이 mid 작다면
            right = mid - 1; // right을 중앙으로
        }else {
            left = mid + 1; // target이 mid 크다면 left를 중앙으로
        }
    }
        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);
        }
    }