[알고리즘] 이진 탐색(Binary Search)

정렬된 데이터에서 탐색 범위를 절반씩 줄여나가면서 특정 값을 찾는 알고리즘

탐색할 때마다 원소의 개수가 절반으로 줄어들기 때문에 속도가 빠르다

시간복잡도 - O(log N)

1. 정렬된 배열에서 배열의 중간값(mid)을 구한다.
2. 중간값과 탐색 값(target)을 비교한다.
      - 중간 값과 탐색 값이 같으면 종료(mid == target)
      - 중간 값보다 탐색 값이 크면 중간 값 기준 오른쪽 구역을 탐색(mid < target)
      - 중간 값보다 탐색 값이 작으면 중간 값 기준 왼쪽 구역을 탐색(mid > target)
3. 탐색 값이 나올 때까지 이 과정을 반복한다.

 

 

이진탐색 예시

int[] arr ={0, 2, 4, 6, 8, 10, 12, 14, 16}이고, target=4인 경우, 이진 탐색으로 target을 찾는 방법은 다음과 같다.

---

이진탐색을 구현하는 방법에는 2가지가 있다.

1. 재귀함수를 이용한 이진 탐색

/**
 * int[] arr : 정렬된 전체 배열
 * int target: 찾고자 하는 값
 * int start : 탐색 시작 인덱스
 * int end : 탐색 끝 인덱스
 * */

public static int binarySearchByRecursion(int[] arr, int target, int start, int end) {
    //시작인덱스가 끝 인덱스보다 크면 탐색 종료
    if(start > end) {
        return -1;
    }

    int mid = (start + end) / 2;    //중간 값의 인덱스
    if(arr[mid] == target) {    //중간값과 찾고자 하는 값(target)이 같으면 중간값 반환
        return mid;
    } else if (arr[mid] > target) { //중간값이 찾고자 하는 값(target)보다 큰 경우 왼쪽 탐색
        return binarySearchByRecursion(arr, target, start, mid - 1);
    } else {    //중간값이 찾고자 하는 값(target)보다 작은 경우 오른쪽 탐색
        return binarySearchByRecursion(arr, target, mid + 1, end);
    }
}

 

2. while문을 이용한 이진 탐색

/**
 * int[] arr : 정렬된 전체 배열
 * int target: 찾고자 하는 값
 * int start : 탐색 시작 인덱스
 * int end : 탐색 끝 인덱스
 * */

public static int binarySearch(int[] arr, int target, int start, int end) {
    while (start <= end) {
        int mid = (start + end) / 2;    //중간값
        if(arr[mid] == target) {        //중간값과 찾고자 하는 값(target)이 같으면 중간값 반환
            return mid;
        } else if (arr[mid] > target) { //중간값이 찾고자 하는 값(target)보다 큰 경우 왼쪽 탐색
            end = mid - 1;
        } else {                        //중간값이 찾고자 하는 값(target)보다 작은 경우 오른쪽 탐색
            start = mid + 1;
        }
    }
    return -1;
}