Answer पर Binary Search

Answer पर binary search एक range में एक value guess करने, यह test करने कि यह काम करती है या नहीं, और सबसे अच्छी ढूंढने तक narrow करते रहने जैसा है।

In this page:

Idea
Monotonic Condition
Capacity Example
Steps
Complexity

Syntax

markup

low, high = min_answer, max_answer
while low < high:
    mid = (low + high) // 2
    if is_feasible(mid):
        high = mid
    else:
        low = mid + 1
return low

Idea

किसी array में एक value की position search करने के बजाय, यह technique किसी problem के possible answers की range पर binary search करती है, हर candidate answer को feasibility के लिए test करते हुए बजाय इसे सीधे stored data से compare करने के।

उदाहरण: Idea

#include <iostream>
using namespace std;
int main() {
	cout << "Binary search the range of possible answers, testing feasibility of each midpoint instead of searching an array";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Binary search the range of possible answers, testing feasibility of each midpoint instead of searching an array");
	}
}

print("Binary search the range of possible answers, testing feasibility of each midpoint instead of searching an array")

#include <stdio.h>
int main() {
	printf("Binary search the range of possible answers, testing feasibility of each midpoint instead of searching an array");
	return 0;
}

Monotonic Condition

यह सिर्फ तब काम करता है जब feasibility monotonic हो — मतलब अगर कोई candidate answer काम करता है, इसके एक side का हर 'आसान' candidate भी काम करता है, और दूसरे side का हर 'मुश्किल' candidate नहीं करता। वह monotonic boundary बिल्कुल वही है जो binary search को हर step पर आधे candidates खत्म करने के लिए चाहिए।

उदाहरण: Monotonic Condition

#include <iostream>
using namespace std;
int main() {
	cout << "Only works when feasibility is monotonic: if one candidate works, every easier candidate on one side also works";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Only works when feasibility is monotonic: if one candidate works, every easier candidate on one side also works");
	}
}

print("Only works when feasibility is monotonic: if one candidate works, every easier candidate on one side also works")

#include <stdio.h>
int main() {
	printf("Only works when feasibility is monotonic: if one candidate works, every easier candidate on one side also works");
	return 0;
}

Capacity Example

एक classic example है minimum capacity ढूंढना (एक ship, couriers के एक set, एक Wi-Fi router, वगैरह की) जो दिए constraints के अंदर एक task पूरा कर सके — आप हर possible capacity को efficiently एक-एक करके जांच नहीं सकते, लेकिन आप possible capacities की range पर binary search कर सकते हैं।

उदाहरण: Capacity Example

#include <iostream>
using namespace std;
bool canShip(int weights[], int n, int capacity, int days) {
	int daysNeeded = 1, load = 0;
	for (int i = 0; i < n; i++) {
		if (load + weights[i] > capacity) { daysNeeded++; load = 0; }
		load += weights[i];
	}
	return daysNeeded <= days;
}
int main() {
	int weights[] = {3, 2, 2, 4, 1};
	cout << (canShip(weights, 5, 6, 2) ? "Feasible" : "Not feasible");
	return 0;
}

public class Main {
	static boolean canShip(int[] weights, int capacity, int days) {
		int daysNeeded = 1, load = 0;
		for (int w : weights) {
			if (load + w > capacity) { daysNeeded++; load = 0; }
			load += w;
		}
		return daysNeeded <= days;
	}
	public static void main(String[] args) {
		int[] weights = {3, 2, 2, 4, 1};
		System.out.println(canShip(weights, 6, 2) ? "Feasible" : "Not feasible");
	}
}

def can_ship(weights, capacity, days):
    days_needed = 1
    load = 0
    for w in weights:
        if load + w > capacity:
            days_needed += 1
            load = 0
        load += w
    return days_needed <= days

weights = [3, 2, 2, 4, 1]
print("Feasible" if can_ship(weights, 6, 2) else "Not feasible")

#include <stdio.h>
int canShip(int weights[], int n, int capacity, int days) {
	int daysNeeded = 1, load = 0;
	for (int i = 0; i < n; i++) {
		if (load + weights[i] > capacity) { daysNeeded++; load = 0; }
		load += weights[i];
	}
	return daysNeeded <= days;
}
int main() {
	int weights[] = {3, 2, 2, 4, 1};
	printf(canShip(weights, 5, 6, 2) ? "Feasible" : "Not feasible");
	return 0;
}

Steps

Pattern है: answer के लिए reasonable lower और upper bounds चुनें, midpoint को एक feasibility check function से test करें, और result के आधार पर range को feasible या infeasible values की ओर narrow करें, बिल्कुल जैसे standard binary search एक target की ओर narrow होता है।

उदाहरण: Steps

#include <iostream>
using namespace std;
int main() {
	cout << "Pick lower/upper bounds for the answer, test the midpoint with a feasibility check, then narrow the range";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Pick lower/upper bounds for the answer, test the midpoint with a feasibility check, then narrow the range");
	}
}

print("Pick lower/upper bounds for the answer, test the midpoint with a feasibility check, then narrow the range")

#include <stdio.h>
int main() {
	printf("Pick lower/upper bounds for the answer, test the midpoint with a feasibility check, then narrow the range");
	return 0;
}

Complexity

Overall running time binary search steps की संख्या (O(log(range))) को feasibility check खुद चलने में जितना समय लगता है उससे multiply किया गया है — इसलिए यह technique सिर्फ तब fast है अगर feasibility check खुद efficient है।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Total time is O(log(range)) binary search steps times the cost of each feasibility check";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Total time is O(log(range)) binary search steps times the cost of each feasibility check");
	}
}

print("Total time is O(log(range)) binary search steps times the cost of each feasibility check")

#include <stdio.h>
int main() {
	printf("Total time is O(log(range)) binary search steps times the cost of each feasibility check");
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Binary Search Next Lesson → Ternary Search