이진 탐색(Binary Search) 이란 ?

이진 탐색 ?

• 이진탐색은 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색하는 알고리즘

---

순차 탐색(Sequential Search)

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
• 가장 기본적인 형태의 데이터 탐색 알고리즘
• 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소의 데이터를 확인해 가며 탐색한다.
• 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다

이진 탐색(Binary Search)

• 기본적으로 리스트 데이터가 정렬되어 있어야 사용할 수 있는 알고리즘이다.
• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는것이 특징이다.
• 이진 탐색은 한 번 확인할 때마다 확인할 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(㏒𝑁)이다.
• 처리해야 할 데이터 개수나 값이 1000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(㏒𝑁)의 속도를 내야 하는 알고리즘을 적용하자
• 찾고자 하는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다.

동작 이해하기 

1. 찾고자 하는 데이터: 4라고 가정하고 아래와 같이 리스트의 시작점: 0, 끝점: 9, 중간점: 4(소수점 이하 제거)을 찾는다.

2. 찾고자 하는 데이터와 중간점의 데이터를 비교한다.

찾고자 하는 데이터는 4이고 중간점[4]의 데이터는 8이기 때문에 찾고자 하는 데이터보다 중간점[4]이 크다.

아래와 같이 중간점에서 부터 끝점 데이터는 찾을 필요가 없기 때문에 끝점[9]을 중간점에서 -1 index한 끝점[3]으로 변경한다.

3. 중간점[1]의 데이터보다 찾고자하는 데이터가 크기 때문에 시작점[0]의 위치를 중간점 오른쪽으로 옴겨준다.

중간점[2]의 데이터가 찾고자 하는 데이터와 동일하기 때문에 탐색을 종료 한다.

시간 복잡도

• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 ㏒₂𝘕에 비례한다.
• 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개 가량의 데이터만 남게 된다
  • 2단계를 거치면 8개 가량의 데이터만 남는다.
  • 3단계를 거치면 4개 가량의 데이터만 남는다
• 다시 말해 이진 탐색은 탐색 범위를 절만씩 줄이며, 시간 복잡도는 O(㏒𝑁)를 보장합니다.

샘플 코드

def binary_search(array, target, start, end):
    if start > end:
        return None

    mid = (start + end) // 2

    if array[mid] == target:
        # 찾은 경우 중간점 인덱스 반환
        return mid
    elif array[mid] > target:
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽으로 확인
        return binary_search(array, target, start, mid - 1)
    else:
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽으로 확인
        return binary_search(array, target, mid + 1, end)


array = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
index = binary_search(array, 4, 0, len(array) - 1)
print('인덱스 위치: ', index, '값 : ', array[index])

public class BinarySearch {

    public int binarySearch(int[] array, int target, int start, int end) {
        if (start > end) {
            return -1;
        }

        int mid = (start + end) / 2;

        if (array[mid] == target) {
            // 찾는 값(target)을 찾은 경우
            return mid;
        } else if (array[mid] > target) {
            // 찾는 값(target)보다 작은 경우 끝점(end)을 중간점(mid) - 1 으로 이동
            // 현재 중간점(mid)보다 target이 작기 때문에 mid - 1로 변경
            return binarySearch(array, target, start, mid - 1);
        } else {
            // 찾는 값(target)보다 큰 경우 시작점(start)을 중간점 + 1 으로 이동
            // 현재 중간점(mid)보다 target이 크기 때문에 시작점(start)을 mid + 1로 변경
            return binarySearch(array, target, mid + 1, end);
        }

    }

    public static void main(String[] args) {

        BinarySearch binarySearch = new BinarySearch();
        int[] array = new int[]{1, 3, 5, 6, 9, 11, 13, 15, 17, 19};
        int index = binarySearch.binarySearch(array, 5, 0, array.length - 1);

        System.out.println("target index: " + index);
    }
}