이분탐색

이분탐색 (Binary Search)

• 전체 범위를 이분할하여 가운데의 값을 비교하여 두 영역 중 다른 영역으로 이동하여 탐색
• 시간복잡도 : O(logN)
• 탐색 전 리스트가 반드시 정렬되어 있어야함 -> 배열을 적게 탐색하는 경우 이분탐색 쓰지 않는 것이 나을수도 있음

 

순차 탐색 vs 이분 탐색

정렬이 안되어있다면 상황에 따라 순차탐색이 더 나을 수도 있다

 

 

java

public class BinarySearch {
	static int[] arr = {1, 3, 5, 7, 8, 10, 20, 35, 99, 100};

	public static void main(String[] args) {
		System.out.println("1. 순환 호출을 이용한 이진 탐색");
		System.out.println(binarySearch1(5, 0, arr.length-1)); // 2
		
		System.out.println("\n2. 반복을 이용한 이진 탐색");
		System.out.println(binarySearch2(20, 0, arr.length-1)); // 6
		
	}
	
	// 재귀적 탐색
	static int binarySearch1(int key, int low, int high) {
		int mid;
		
		if(low <= high) {
			mid = (low + high) / 2;
			
			if(key == arr[mid]) { // 탐색 성공 
				return mid;
			} else if(key < arr[mid]) {
				return binarySearch1(key ,low, mid-1); // 왼쪽 부분 탐색 
			} else {
				return binarySearch1(key, mid+1, high); // 오른쪽 부분 탐색 
			}
		}
		
		return -1; // 탐색 실패 
	}
	
	// 반복적 탐색
	static int binarySearch2(int key, int low, int high) {
		int mid;
		
		while(low <= high) {
			mid = (low + high) / 2;
			
			if(key == arr[mid]) {
				return mid;
			} else if(key < arr[mid]) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		
		return -1; // 탐색 실패 
	}

}

 

c++

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

 

 

Parametric Search

• 이분탐색을 활용하되, 정확한 값이 아닌 가장 근사한 값 찾는 기법
• 방정식 f(x)가 있다면, 값에 최대한 근사한 해를 찾는 기법
• 즉, 찾는 값 자체를 비교하는 것이 아닌 값을 식에 대입하여 나온 결과물 비교해야함
• 최적으로 구할 해를 이분탐색으로 찾는 것

언제 사용하는게 좋을까? 

구해야 할 값의 범위가 매우 크다면( 즉, 완전탐색 계산이 불가능) 고려

 

public static long binarySearch(int need){
    long s = 0;
    long e = 2_000_000_000;
    long returnHeight = 0;

    while(s <= e){
        long mid = (s + e) / 2;

        // 기준값 설정
        // 자른 값들의 총합을 이용
        long sum = 0;
        for(int i = 0; i<arr.length; i++){
            int ele = arr[i];
            if(ele > mid)
                sum += ele - mid;
        }

        if(sum >= need) { // 조건을 만족하므로 범위를 더 엄밀하게 줄임
            s = mid + 1;
            returnHeight = mid;    // 조건을 충족한다면 일단 저장
        }else if(sum < need)
            e = mid - 1;
    }
    return returnHeight;
}

 

 

참고 - https://github.com/VSFe/Algorithm_Study?tab=readme-ov-file