이진 탐색

탐색범위를 1/2씩 줄여나가는 방식으로 일반 탐색보다 빠른 탐색법이다.

정렬된 배열에서 탐색하는 방법.

1. 데이터 집합의 중앙에 있는 요소를 고릅니다.

2. 중앙 요소의 값과 찾고자 하는 목표 값을 비교합니다.

3.목표 값이 중앙 요소의 값보다 작다면 중앙을 기준으로 데이터 집합의 외편에 대해 새로 검색을 수행하고 크다면 오른쪽에 대해 탐색을 수행한다.

4. 1~3단계를 반복한다

소스코드

#include <iostream>
 
using namespace std;
 
int* BinarySearch(int* InputData, int Size, int target)
{
    int Left= 0;
    int Right = (Size / 2) - 1;
    int    Mid;
 
    while (Left <= Right)
    {
        Mid = (Left + Right) / 2;
 
        if (target == InputData[Mid])
            return &(InputData[Mid]);
        else if (target > InputData[Mid])
            Left = Mid + 1;
        else
            Right = Mid - 1;
    }
    return NULL;
}
 
int main()
{
    int arr[5] = { 1,2,3,4,5 };
    int T = 2;
    int *Result = NULL;
 
    Result = BinarySearch(arr, 5, 1);
 
    cout << (*Result) << endl;
 
    return 0;
}