Binary Search

  • 오름 차순 정렬 되어 있을 때 특정 값의 위치를 찾는 알고리즘
  • log_{2}n 시간 복잡도, 선형탐색보다 매우 빠름
#include <iostream>
using namespace std;
#define MAX_M 100

void binarySearch(int* arr, int left, int right, int target)
{
    int mid;
    if (left > right)
    {
        cout << "No value in list" << endl;
        return;
    }

    mid = (left + right) / 2;

    if (target < arr[mid])
    {
        binarySearch(arr, left, mid - 1, target);
    }
    else if (arr[mid] < target)
    {
        binarySearch(arr, mid + 1, right, target);
    }
    else
    {
        cout << "found idx " << mid << endl;
        return;
    }
}

int main(void)
{
    int targetValue;
    int arr[MAX_M] = { 1, 2, 4, 5, 7, 9, 11 };

    cin >> targetValue;
    
    binarySearch(arr, 0, 6, targetValue);

    return 0;
}

 

You may also like...