[알고리즘] Binary Search : 이분 탐색

저 녹아요....

---

1. 이분탐색이란?

"반으로 쪼개기"라는 원리를 기반으로 하며, 탐색 범위를 지속적으로 반씩 줄여나가면서 값을 찾는다.

시간복잡도 : O(logn)

 

 

2. 예시

left = mid + 1 / right = mid - 1로 업데이트 하는 이유?

• mid 값이 이미 target보다 작기 때문에, target은 최소한 mid + 1 위치에 있을 수밖에 없기 때문!
• mid 값이 이미 target보다 크기 때문에, target은 최소한 mid - 1 위치에 있을 수 밖에 없기 때문!

 

3. 주의점

정렬된 배열에서만 사용 가능하다.

 

이분탐색의 원리를 생각해보면 당연하다.

우리가 이분탐색을 가능하게 하는 이유가, 다시 말해서 left, right값을 업데이트할 수 있는 이유가, 그 사이에는 우리가 원하는 숫자가 없을 것이라는 '믿음'을 가지고 건너뛰는 것이기 때문이다.

 

그렇다면 이런 의문을 제기할 수 있다.

정렬되기만 하면 되는 거 아닌가요? 내림차순으로 정렬되면요? 

불가능하지는 않다. 하지만 관습적으로 오름차순 배열을 사용한다. 하고 싶으면 하세요!

 

 

4. 코드(c++)

bool binary_search(vector<int>& arr, int len, int target){
	int left = 0, right = len - 1;
    
    while(left <= right){
    	int mid = (left + right) / 2;
        
        //원하는 값을 찾았다면 true 반환
        if(target == arr[mid])	return true;
        
        // 원하는 값이 더 작다면 검사 범위를 더 낮게 잡아야 한다.
        if(target < arr[mid]){
        	right = mid - 1;
        }
        // 원하는 값이 더 크다면 검사 범위를 더 크게 잡아야 한다.
        else if(target > arr[mid]){
        	left = mid + 1;
        }
    }
    return false; // 마지막까지 못찾는다면 false 반환
}

만약 예시 상황에서 left,right가 겹쳤을 때, 그리고 그때의 arr[mid]가 우리가 원하는 값이 아니었다면? 

코드에 따라, 우리는 다시 한번 left 또는 right값을 업데이트 했을 것이고, 이때 left와 right값이 역전되므로 while문을 탈출하게 된다.

우리가 while문을 돌 동안 원하는 값을 찾지 못했으므로 결국 배열에는 target이 애초에 존재하지 않았던 것이다. 따라서 false를 반환한다.