← Back to DSA Course | Chapter 10: Searching Algorithms | Lesson 2 of 5

Binary Search क्या है

Binary search उस guessing game जैसा है जहां आप हमेशा middle number चुनते हैं और आपको बताया जाता है higher या lower, हर बार possibilities को आधा काटते हुए।

In this page:

  1. What is Binary Search
  2. How It Works
  3. Search Boundaries
  4. Complexity
  5. Common Variation
Syntax
markup 
low, high = 0, len(arr) - 1
while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
return -1

What is Binary Search

Binary search sorted data में एक target value बार-बार middle element जांचकर और target छोटा है या बड़ा इसके आधार पर बचे range का आधा खत्म करके ढूंढता है — यह सिर्फ इसलिए काम करता है क्योंकि data sorted है, जो आपको पूरे आधे को बिना जांचे खारिज करने देता है।

उदाहरण: What is Binary Search

#include <iostream>
using namespace std;
int main() {
	int arr[] = {1, 3, 5, 7, 9, 11};
	int target = 7, low = 0, high = 5;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (arr[mid] == target) { cout << "Found at index " << mid; break; }
		else if (arr[mid] < target) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {1, 3, 5, 7, 9, 11};
		int target = 7, low = 0, high = 5;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (arr[mid] == target) { System.out.println("Found at index " + mid); break; }
			else if (arr[mid] < target) low = mid + 1;
			else high = mid - 1;
		}
	}
}
arr = [1, 3, 5, 7, 9, 11]
target = 7
low, high = 0, 5
while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        print("Found at index", mid)
        break
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
#include <stdio.h>
int main() {
	int arr[] = {1, 3, 5, 7, 9, 11};
	int target = 7, low = 0, high = 5;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (arr[mid] == target) { printf("Found at index %d", mid); break; }
		else if (arr[mid] < target) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}

How It Works

हर step पर, target की तुलना current range के midpoint की value से करें: अगर वे match करें, आप खत्म; अगर target छोटा है, right half discard करें और left half search करें; अगर बड़ा है, left half discard करें और right half search करें।

उदाहरण: How It Works

#include <iostream>
using namespace std;
int main() {
	int arr[] = {1, 3, 5, 7, 9, 11};
	int target = 3, low = 0, high = 5;
	while (low <= high) {
		int mid = (low + high) / 2;
		cout << "mid=" << mid << " value=" << arr[mid] << endl;
		if (arr[mid] == target) break;
		else if (arr[mid] < target) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {1, 3, 5, 7, 9, 11};
		int target = 3, low = 0, high = 5;
		while (low <= high) {
			int mid = (low + high) / 2;
			System.out.println("mid=" + mid + " value=" + arr[mid]);
			if (arr[mid] == target) break;
			else if (arr[mid] < target) low = mid + 1;
			else high = mid - 1;
		}
	}
}
arr = [1, 3, 5, 7, 9, 11]
target = 3
low, high = 0, 5
while low <= high:
    mid = (low + high) // 2
    print("mid=", mid, "value=", arr[mid])
    if arr[mid] == target:
        break
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
#include <stdio.h>
int main() {
	int arr[] = {1, 3, 5, 7, 9, 11};
	int target = 3, low = 0, high = 5;
	while (low <= high) {
		int mid = (low + high) / 2;
		printf("mid=%d value=%d\n", mid, arr[mid]);
		if (arr[mid] == target) break;
		else if (arr[mid] < target) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}

Search Boundaries

दो pointers, आमतौर पर low और high कहलाते हैं, current search range की boundaries मार्क करते हैं; midpoint हर step उनके बीच calculate होता है, और आधा range खत्म करने के बाद, दो boundaries में से एक अगले comparison के लिए range सिकोड़ने के लिए move होती है।

उदाहरण: Search Boundaries

#include <iostream>
using namespace std;
int main() {
	int low = 0, high = 5;
	int mid = (low + high) / 2;
	cout << "low=" << low << " high=" << high << " mid=" << mid;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int low = 0, high = 5;
		int mid = (low + high) / 2;
		System.out.println("low=" + low + " high=" + high + " mid=" + mid);
	}
}
low, high = 0, 5
mid = (low + high) // 2
print("low=", low, "high=", high, "mid=", mid)
#include <stdio.h>
int main() {
	int low = 0, high = 5;
	int mid = (low + high) / 2;
	printf("low=%d high=%d mid=%d", low, high, mid);
	return 0;
}

Complexity

Binary search O(log n) time लेता है क्योंकि हर comparison बचे search space को आधा करता है, और सिर्फ दो boundary pointers के साथ iteratively किए जाने पर O(1) extra space — बड़े sorted datasets पर linear search के O(n) से एक नाटकीय improvement।

उदाहरण: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Binary search: O(log n) time, O(1) extra space when done iteratively";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Binary search: O(log n) time, O(1) extra space when done iteratively");
	}
}
print("Binary search: O(log n) time, O(1) extra space when done iteratively")
#include <stdio.h>
int main() {
	printf("Binary search: O(log n) time, O(1) extra space when done iteratively");
	return 0;
}

Common Variation

जब sorted data में duplicate values हों, एक standard binary search किसी भी एक matching element पर land हो सकता है — एक आम variation सिर्फ किसी match के बजाय target का specifically पहला (या आखिरी) occurrence ढूंढने के लिए comparison logic adjust करता है।

उदाहरण: Common Variation

#include <iostream>
using namespace std;
int main() {
	cout << "With duplicates, a standard binary search may land on any matching index, not necessarily the first or last";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("With duplicates, a standard binary search may land on any matching index, not necessarily the first or last");
	}
}
print("With duplicates, a standard binary search may land on any matching index, not necessarily the first or last")
#include <stdio.h>
int main() {
	printf("With duplicates, a standard binary search may land on any matching index, not necessarily the first or last");
	return 0;
}
Related Topics

Answer पर Binary Search · Binary Search Tree क्या है · Binary Tree परिचय · Linear Search क्या है

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. एक unsorted array पर binary search चलाना, जो गलत answers देता है।
  2. low <= high के बजाय while (low < high) उपयोग करना, जो आखिरी बचा element miss करता है।
  3. mid + 1 या mid - 1 के बजाय low = mid या high = mid सेट करना, जो हमेशा के लिए loop करता है।
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Linear Search Next Lesson → Binary Search on Answer

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.