이진 탐색 정리

정렬 (Sorting)

🔍 개요

• 전제 조건 : 반드시 정렬 된 상태여야 함
• 시간 복잡도 : O(log N)

---

📚 기본 로직

int binarySearch(int[] arr, int target) {
	int left = 0;
	int right = arr.length - 1;
	
	while(left <= right) {
		int mid = (left + right) / 2;
		if(arr[mid] == target) {
			return mid; // 찾음
		} else if(arr[mid] < target) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return -1; // 못 찾음
}

---

⚡️ 응용 패턴

(A) Lower Bound & Upper Bound

• Lower Bound : target 이상이 처음 나오는 위치
• Upper Bound : target 초과가 처음 나오는 위치

// Arrays.binarySearch는 정확히 같은 값만 찾음 -> 보통 직접 구현
int lowerBound(int[] arr, int target) {
	int left = 0;
	int right = arr.length;
	
	while(left <= right) {
		int mid = (left + right) / 2;
		if(arr[mid] >= target) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
}
 
int upperBound(int[] arr, int target) {
	int left = 0;
	int right = arr.length;
	
	while(left <= right) {
		int mid = (left + right) / 2;
		if(arr[mid] > target) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
}

(B) 답을 범위에서 탐색 (Parametric Search)

• 아이디어 : “조건을 만족하는 값 중 가장 작은/큰 것”을 찾는 방식
• 형태
  • while (left <= right) 형태로 범위 좁혀감
  • mid 값으로 조건 검사 → 조건 만족하면 범위 줄이기

(예시 : 랜선 자르기 문제)

long binarySearch(long[] arr, long target) {
	long left = 1;
	long right = Arrays.stream(arr).max().getAsLong();
	long ans = 0;
	
	while(left <= right) {
		long mid = (left + right) / 2;
		long count = 0;
		for(long x : arr) {
			count += (x / mid);
		}
		
		if(count >= target) { // 조건 만족 -> 더 크게 자를 수 있는지 확인
			ans = mid;
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return ans;
}