[알고리즘] 이분 탐색

컴퓨터는 1억번 연산하는데 약 1초가 걸린다. 하지만 알고리즘 문제를 해결하다 보면 입력이 1억번 이상 주어지는 경우가 있다.

이때에는 모두 탐색할 경우 시간 초과가 날 가능성이 크다. 따라서 더 빠른 풀이방법을 생각해야 한다. 이런 경우 보통 이분탐색을 쓴다.

 

선형 탐색의 시간 복잡도를 O(lon N)으로 만들어준다.

 

 

[반복문으로 구현한 이분 탐색]

while(L <= R){
    M = (L + R) /  2;
    if(target > arr[M]) L = M + 1;
    else if(target < arr[M]) R =  M - 1;
    else {
        result = true;
        break;
    }
}

lower_bound

upper_bound