Binary Search (이분탐색)

Binary Search는 정렬되어 있는 리스트에서 탐색 범위를 좁혀가며 원하는 값을 얻는 알고리즘이다.

리스트가 반드시 정렬되어 있어야 하며, 3개의 변수 (low, mid, high)를 사용해서 값을 탐색한다.

중앙값(mid)을 기준으로 비교하여 low와 high 값을 정하고, 이 과정을 반복해서 값을 얻어내면 된다.

 

탐색 범위가 반으로 줄어들면서 start와 end 값을 정하는 과정을 거치기 때문에 시간복잡도가 낮고, 순차적 탐색보다 빠른 탐색이 가능하므로 배열의 원소 개수가 많을 때 주로 사용된다. 

 

🕹️ Binary Search 과정

1️⃣ 배열의 중간 값을 계산하여 찾고자 하는 값과 비교한다. 중간 값은 (low+high)/2 로 계산한다. 

2️⃣ 중간 값이 찾고자 하는 값보다 작다면 중간값보다 1만큼 증가시킨 값을 low (low = mid+1)로 정하고 중간 값 기준 오른쪽 부분에서 탐색을 진행하고, 중간값이 찾고자 하는 값보다 크다면 중간값보다 1만큼 감소시킨 값을 high (high = mid-1)로 정하고 중간 값 기준 왼쪽 부분에서 탐색을 진행한다. 

3️⃣ 이 과정을 찾고자 하는 값을 구할 때까지 반복한다. 

 

 

👩‍💻 Binary Search 코드 구현

 

while문으로 구현

public class BinarySearchTest{
	static int[] arr;
    
    public static void main(String[] args){
    	arr = new int[]{1,3,5,7,9,11,13};
        int idx = findBsIdx(9);
        System.out.println(idx);
    }
    
    public static int findBsIdx(int target){
    	int low = 0;
        int high = arr.length-1;
        int mid;
        int answer=0;
        
        while(low<=high){
        	mid = (low+high)/2;
            
            if(arr[mid]<target){
            	low = mid+1;
            }else if(arr[mid]>target){
            	high = mid-1;
            }else{
            	answer = mid;
            }
        }
        
        if(answer==0) answer =-1; // 최종 탐색 불가할 경우 -1 반환 
        
        return answer;
    }
}

 

재귀함수로 구현

public static int binarySearch(int[] arr, int low, int high, int key) {
    
    if (high >= low) {

        int mid = low + (high - low) / 2;

        if (arr[mid] == key) {
            return mid;
        }
        // 중간 값이 키보다 큰 경우 : 낮은 인덱스와 중간 인덱스에서 1을 뺀 값을 가지고 함수를 재귀적으로 호출
        else if (arr[mid] > key) {
            return binarySearch(arr, low, mid - 1, key);
        }
        // 중간 값이 키보다 작은 경우 : 중간 인덱스에 1을 더하고 높은 인덱스와 함께 함수를 재귀적으로 호출
        else {
            return binarySearch(arr, mid + 1, high, key);
        }
    }

    // 높은 인덱스가 낮은 인덱스보다 작으면 배열에서 키를 찾지 못했음을 나타내기 위해 -1을 반환
    return -1;
}

 

 

👩‍💻 Binary Search  Lower & Upper

 

이분 탐색 문제를 풀다보면 lower bound와 upper bound를 이용해서 풀어야 하는 것들이 있다.

 

위의 그림처럼 내가 찾고자 하는 값이 3일 때, 3이 시작하는 곳 (가장 왼쪽 index)을 찾기 위해 lower bound를 사용하고 끝나는 곳 (가장 오른쪽 index)을 찾기 위해 upper bound를 사용한다.

Lower bound 값의 결과는 3보다 작은 값이 나오기 직전의 인덱스 값이다.

하지만 upper bound 값의 결과는 3이 마지막으로 위치하는 인덱스가 아닌, 그 다음 인덱스 값을 갖게 된다. 

 

만약 찾고자 하는 값이 배열에 없는 값인 8이라면, 8보다 작은 값 중 최대인 7을 나타내는 인덱스(8) 바로 다음 값(9=last)이 lower bound와 upper bound 값이다. 

 

Lower Bound 구현

public static int lowerBound(target, arr) {
    int left = 0;
    int right = arr.length; //lower bound가 arr의 길이를 넘어갈 수 있음

    while (left < right) { // left가 right와 같아지게 되면 out of index가 될 수 있음
        int mid = (left + right) / 2;

        if (target <= arr[mid]) { 
            right = mid; 
        } else {
            left = mid + 1; 
        }
    }
    return left;
}

 

Upper Bound 구현 

public static int upperBound(target, arr) {
    int left = 0;
    int right = arr.length; 

    while (left < right) {
        int mid = (left + right) / 2;

        if (target >= arr[mid]) { 
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

 

⏳ 탐색기법 시간복잡도 비교

• 순차적 탐색 : 최악의 경우에는 끝까지 탐색해야 함 ➡️ (O(n))
• 이분 탐색 : 탐색 범위가 1/2씩 줄어듦 ➡️ (O(log n))

 

 

 

 

참고

https://adjh54.tistory.com/187

https://enumclass.tistory.com/178