[알고리즘] Binary Search(이진 탐색/이분 탐색)이란?

Binary Search(이진 탐색/이분 탐색)

이진 탐색 알고리즘은 정렬되어 있는 배열에서 찾고자 하는 특정한 값을 찾아내는 알고리즘입니다.

이진 탐색 알고리즘이 탐색하는 방식은 배열의 중간에 있는 값(mid)을 선택하여 찾고자하는 값(x)과 비교합니다.

찾고자하는 값(x)가 중간 값(mid)보다 작으면 중간 값을 기준으로 왼쪽으로 다시 탐색, 크다면 오른쪽으로 다시 탐색합니다.

다시 탐색을 시작할 때 찾고자하는  값(x)가 중간 값(mid)보다 작으면 해당 중간 값부터 우측 끝값을 제거하고 다시 중간 값을 선택하고 찾고자하는 값(x)을 찾습니다.

반대로 찾고자하는 값(x)가 중간 값(mid)보다 크면 해당 중간 값부터 좌측 끝값을 제거 하고 다시 중간 값을 선택하고 찾고자하는 값(x)를 찾습니다.

찾고자 하는 값(x)과 중간 값(mid)가 일치할 때 까지 이 과정을 반복합니다. (x = mid면 종료)

만약 low값보다 high값이 작다면 더 이상 검색할 범위가 없어 검색 실패로 종료됩니다.

 

이진 탐색 과정

중간 값은 다음과 같은 식으로 구할 수 있습니다.

 

주어진 배열의 값이 아래와 같고 찾고자 하는 값(x)이 41이라고 했을 때 탐색 과정을 봅시다.

 

1. 배열의 시작 지점이 low가 되고 끝 지점이 high가 되며 이 두 값을 이용해 mid값을 구합니다.

 

2. 중간 값 18은 찾고자 하는 값 41보다 작으므로 해당 중간 값부터 좌측 끝값을 제거 하고 우측부터 시작해 다시 중간 값을 선택하고 찾고자하는 값(x)를 찾습니다.

3. 중간 값 41과 찾고자 하는 값 41과 일치하므로 종료됩니다.

---

이진 탐색 알고리즘 코드 (Java)

package algorithm;

public class Binarysearch {
    public static void main(String[] args) {
        int[] arr = {10, 13, 17, 30, 41, 45};
        binarySearch(arr, 41);
    }

    public static int binarySearch(int arr[],  int findKey) {
        int low = 0;
        int high = arr.length - 1;

        // low가 high보다 작거나 같을 때 까지 반복.
        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == findKey) {
                return mid;
            }
            if (arr[mid] > findKey) {
                high = mid - 1;
            }
            if (arr[mid] < findKey) {
                low = mid + 1;
            }
        }
        // low > high 이라면 -1을 반환하고 종료.
        return -1;
    }
}

출력문으로 실행 결과를 보면 41을 찾을 시 arr에서 41이 위치한 index 4를 반환합니다.

 

이진 탐색 알고리즘 코드 (Python3)

def binarySearch(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = low + (high - low) // 2

        if arr[mid] == target:
            return True

        if target < arr[mid]:
            high = mid - 1
        if target > arr[mid]:
            low = mid + 1
    
    return False