이진검색

이진검색(Binary Search)

자료의 가운데부터 검색하고 가운데 값보다 값이 작으면 왼쪽으로 크면 오른쪽으로 탐색

이진검색을 하기 위해서는 자료가 정렬된 상태이어야 함

<재귀로 구현>

#include <iostream>
using namespace std;

int target = 7;
int f(int* arr, int front, int end);
int main(){
    int arr[] = { 2, 4, 7, 9, 11, 19, 23 };
    int n = sizeof(arr) / sizeof(int);
    int ans = f(arr, 0, n - 1);
    if (ans != -1){
        cout << ans;
    }
    else
        cout << "no find";
}
int f(int* arr, int front, int end){
    int mid = (front + end) / 2;
    if (front > end){
        return -1;
    }
    if (arr[mid] == target){
        return mid;
    }
    else if (target < arr[mid]){
        return f(arr, front, mid - 1);
    }
    else{
        return f(arr, mid + 1, end);
    }
}