[알고리즘] 이분 탐색

이분탐색(Binary Search)이란, 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

1. 구현방법

• 라이브러리 사용

단, 이 녀석은 bool 타입으로 배열내 해당 수가 존재하는지 찾아주는 역할만 한다.

#include <algorithm>

int main(){
	int arr[n];
    
    bool ok = binary_serach (arr, arr+n, 70);

• 반복문을 통한 직접구현

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){
        	return true;
        } else if (arr[mid] > key) {
        	end = mid - 1;
        } else {
        	start = mid + 1;
        }
    }
    return false;
}