[알고리즘] 이진탐색

1. 이진탐색

이진탐색은 정렬된 배열에서 특정값을 효율적으로 찾는 알고리즘입니다.

가장 먼저 가운데 값을 탐색합니다. 그리고 찾는 값이 가운데값보다 크다면 오른쪽 그룹을 살펴보고 작다면 왼쪽 그룹을 살펴봅니다. 그리고 해당 그룹의 가운데 값을 탐색합니다. 이를 재귀적으로 반복하여 원하는 값을 찾는 탐색이 이진탐색입니다.

전체를 순회하는 것보다 절반씩 나누고 필요없는 부분은 순회하지 않으므로 효율적인 알고리즘입니다.

다만 이진탐색 방식 때문에 정렬된 배열에서만 효과가 있다는 단점이 있습니다.

 

이를 파이썬과 자바코드로 확인해보겠습니다

 

파이썬

def binary_search_iter(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

arr = [2, 4, 6, 8, 10, 12]
target = 10
print(binary_search_iter(arr, target))  # 4

 

자바

public class BinarySearchIterative {
    public static int binarySearchIter(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10, 12};
        int target = 10;
        System.out.println(binarySearchIter(arr, target));  // 4
    }
}

 

2) 내장 라이브러리

파이썬에는 이진탐색에 대한 내장 라이브러리가 존재합니다.

사용방법은 아래와 같습니다.

import bisect

nums = [1, 3, 4, 4, 5, 7]

# 4의 왼쪽 인덱스
print("target left::",bisect.bisect_left(nums, 4))   # target left:: 2


# 없는 숫자를 입력할 경우 타겟값보다 크면서 가장 작은 인덱스 값인 5 -> 왼쪽이므로 5-1 = 4
print("target left::",bisect.bisect_left(nums, 6))   # target left:: 4

# 4의 오른쪽 인덱스
print("target right::",bisect.bisect_right(nums, 4))  # target right:: 4

## 타겟의 값이 리스트의 가장 마지막보다 크므로 타겟인덱스는 5 -> 오른쪽은 +1이므로 5+1=6
print("target right::",bisect.bisect_right(nums, 9))  # target right:: 6

# 6이 들어갈 위치 -> 정렬된 기준으로 비교, 여기서는 5와 7사이
print(bisect.bisect(nums, 6)) # 5