[Algorithm] Binary Search (이분 탐색)

코딩 테스트 공부를 하다가 Binary Search와 관련하여 문제풀이 방법이 다른 방법이 있어 정리를 한다.

 

📌기존에 자주 쓰던 Binary Search 코드

#include <vector>

int BinarySearch(vector<int> &A, int target)
{
    int N = A.size();
    if(N == 0)
    {
    	return -1;
    }
    
    int l = 0;
    int r = N-1;
    
    while(l<=r)
    {
    	int m = (l + r) / 2;
    	if(A[m] == target){
        	return m;   
        }
        else if(A[m] > target){
        	r = m - 1;
        }
        else{
        	l = m + 1;
        }
    }
    return -1;
 }

이 코드에서 문제점이 있다.

바로 int m 을 구하는 과정에서 값이 커질 경우 overflow 문제가 발생한다.

 

int 형의 경우 –2,147,483,648 ~ 2,147,483,647 사이의 값을 가지기 때문에 ( l + r ) 의 값이 이 범위를 벗어나는 순간 overflow 가 발생 할 수 있다.

 

따라서 아래와 같이 코드를 써 줄 수 있다.

 

📌두번째 Binary Search 코드

#include <vector>

int BinarySearch(vector<int> &A, int target)
{
    int N = A.size();
    if(N == 0){
    	return -1;
    }
    int l = 0;
    int r = N - 1;
    while(l < r){
    	int m = l + ((r - l + 1) / 2);
        if(A[m] > target){
        	r = m - 1;
        }else{
        	l = m;
        }
    }
    if(l == r){
    	if(A[l] == target){
        	return l;
        }
    }
    
	return -1;
}

int m = l + ((r - l + 1) / 2);

m을 구하는 위 코드에서 (r - l + 1)을 수행하면서 overflow가 발생하는 것을 막을 수 있다.

 

 

문제를 풀면서 데이터 자료형의 범위 값에 초점을 두고 푸는 습관을 들어야겠다.

---

💻참고자료

자료형 정리 : hyeri0903.tistory.com/112