[분할정복][이진검색] Binary Search

이진 검색 (Binary Search)

정렬된 리스트에서 빠른 시간 안에 찾을 수 있는 방법.

시간복잡도 : O(logN)

 

정렬된 Arr 길이 :  N

찾고자 하는 원소 : Target

* 실수한 부분 : start, end 값을 갱신할 경우 mid + 1 혹은 mid - 1 을 해야한다. 그렇지 않으면 무한루프를 돌게 된다.

start = 0; end = N-1;
while(start<=end){
	mid = (end - start) / 2 + start;
    if(arr[mid] == target) break;
    else if(arr[mid] > target) end = mid - 1;
    else start = mid + 1;
 }