<algorithm> 이진 탐색

단순 순회 알고리즘으로, 풀수 없는 백준 문제가 생겨나서 이진탐색 알고리즘을 복습하게 되었습니다.

(1654번)

 

이진탐색 이란?

- 정렬된 배열에서 검색 범위를 줄여 나가면서 검색 값을 찾는 알고리즘.

 

시간 복잡도

- O(logN)

 

 

정렬된 배열의 중간값을 임의로 선택하여 찾고자 하는 키(key) 값과 비교하는 탐색 알고리즘.

 

중앙값을 기준으로 왼쪽 오른쪽 탐색을 달리한다.

 

반복, 재귀, STL 이용하여 구현가능

 

//반복문을 이용한 이진탐색을 이용하여 탐색
bool BinarySearch(int *arr, int len, int key){
    int start = 0;
    int end = len-1;
    int mid; 
 
    while(end - start >= 0) {
        mid = (start + end) / 2;    //중앙 값
 
        if (arr[mid] == key) {    //key값을 찾았을때
            return true;
 
        } else if (arr[mid] > key) {   //key값이 mid의 값보다 작을때 (왼쪽으로)
            end = mid - 1;
 
        } else {  //key값이 mid의 값보다 클때 (오른쪽으로)
            start = mid + 1;
 
        }
    }
    return false;
}

 

 

//재귀를 이용한 이진탐색을 이용하여 탐색
bool BinarySearch(int *arr, int start, int end, int key) {
 
    if (start > end) return false; //key 값이 없을 때
 
    int mid = (start + end) / 2;
 
    if (arr[mid] == key) {    //key 값을 찾았을 때
        return true;
        
    } else if (arr[mid] > key) { //key 값이 mid 의 값보다 작을때(왼쪽으로)
        return BinarySearch(arr, start, mid - 1, key);
        
    } else {  //key 값이 mid 의 값보다 작을때(왼쪽으로)
        return BinarySearch(arr, mid + 1, end, key);
        
    }
}

 

#include<iostream>
#include<algorithm>
using namespace std;
 
//STL를 이용한 이진탐색을 이용하여 탐색
int main(void){
    int n= 100;
    int arr[n];
 
    for(int i=0; i<n; i++){
        arr[i] = i;
    }
 
    cout << "exist : " << binary_search(arr, arr+n, 70) << endl;
    
    return 0;
}

(출처)https://blo ckdmask.tistory.com/167

[탐색] 이진탐색 (Binary Search) 구현 방법