이진 탐색 (Binary search)

이진 탐색(Binary search)는 정렬된 데이터 집합을 이분화 하면서 탐색을 진행하는 방법이이다.

검색 범위를 반으로 줄여가며 탐색하기 때문에 순차적으로 탐색하는 것 보다 효율적이다. 이를 위해서는 데이터가 먼저 정렬 되어 있어야 한다. 

1. 입력 데이터의 중앙에 있는 값을 선택
2. 찾고자 하는 값과 (1)의 중앙 값을 비교
3. 찾고자 하는 값보다 (1)이 작을 경우 -> 입력 데이터 중앙 값의 왼쪽에 대한 탐색 진행
4. 찾고자 하는 값보다 (1)이 클 경우 -> 입력 데이터 상 중앙 값의 오른쪽에 대한 탐색 진행
5. 찾고자 하는 값을 찾을 때 까지 1~4를 계속 수행

구현 예

#include <iostream>

int search(int* nums, int numSize, int target)
{
    int left = 0;
    int right = numSize - 1;

    while (left <= right)
    {
        int pivot = (left + right) / 2;
        if (nums[pivot] == target)
        {
            return pivot;
        }
        else if (nums[pivot] < target)
        {
            left = pivot + 1;
        }
        else
        {
            right = pivot - 1;
        }
    }
    return -1;     
}


int main()
{
    int Nums[] = { 1, 3, 4, 6, 7, 15, 20, 21 };
    int Target = 15;

    int result = search(Nums, 8, Target);

    return 1;
}