Lesson 1 � Beginner

Binary Search: Sorted Array mein Search

Binary Search DSA ki sabse efficient searching technique hai. Agar array sorted hai, toh tumhe har element check nahi karna � aadha-aadha eliminate karte jaao. O(log n) time mein answer mil jayega!

? 25 min✓ Beginner✓ Arrays basics

Binary Search hota kya hai?

WHAT

Binary Search ek divide-and-conquer algorithm hai jo sorted array mein element dhundhta hai. Har step mein array ko aadha karta hai � agar target mid se chhota hai toh left half mein dekho, bada hai toh right half mein.

WHEN

Tab use karo jab array sorted ho aur tumhe kisi specific element ki position dhundhni ho. Linear search O(n) leta hai, binary search sirf O(log n) � 1000 elements mein sirf 10 steps!

WHERE

Search problems, insertion position finding, range queries, answer space problems � binary search interview mein bahut zyada use hota hai. Har competitive coding contest mein minimum ek binary search ka question aata hai.

Mental Model: Imagine karo tum ek phone directory mein naam dhundh rahe ho. Agar tumhe pata hai directory alphabetical hai, toh tum beech se kholte ho � agar tumhara naam 'M' se start hota hai toh tum left half rakh dete ho aur sirf right half dekhte ho. Ye hai binary search � har baar aadha eliminate karna!

Visual samjho

Chalo ek example lete hain. Sorted array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Humein 23 dhundhna hai.

Step 1: left=0, right=9, mid=4
Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
 ^
 mid=16
16 < 23 ✓ left = mid+1 = 5

Step 2: left=5, right=9, mid=7
Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
 ^
 mid=56
56 > 23 ✓ right = mid-1 = 6

Step 3: left=5, right=6, mid=5
Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
 ^
 mid=23
23 == 23 ✓ mil gaya! Index = 5 ?

Sirf 3 steps mein mil gaya! Agar linear search karte toh 6 steps lagte (index 0 se 5 tak). Bade arrays mein ye difference bahut zyada hota hai.

Code: Iterative vs Recursive

Do tarike hain binary search likhne ke � iterative (loop) aur recursive (function khud ko call kare). Interview mein dono aana chahiye.

# Iterative Binary Search � Preferred!
def binary_search(arr, target):
 left, right = 0, len(arr) - 1
 while left <= right:
 mid = (left + right) // 2
 if arr[mid] == target:
 return mid
 elif arr[mid] < target:
 left = mid + 1
 else:
 right = mid - 1
 return -1

# Recursive Binary Search
def binary_search_recursive(arr, target, left, right):
 if left > right:
 return -1
 mid = (left + right) // 2
 if arr[mid] == target:
 return mid
 elif arr[mid] < target:
 return binary_search_recursive(arr, target, mid + 1, right)
 else:
 return binary_search_recursive(arr, target, left, mid - 1)

# Usage
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(arr, 23)) # 5
print(binary_search(arr, 100)) # -1

Interview Tip: Iterative version zyada preferred hai kyunki recursion mein stack space O(log n) lagta hai. But recursive version cleaner dikhta hai � agar interviewer bole toh dono bata do. Mid calculation mein (left + right) // 2 integer overflow de sakta hai C++ mein, isliye left + (right - left) // 2 use karo.

Mid Calculation kaise karein?

Mid nikalne ka formula simple hai but ismein ek important subtlety hai:

# Method 1: Basic � Python mein safe hai
mid = (left + right) // 2

# Method 2: Overflow-safe � C++/Java mein zaroori
mid = left + (right - left) // 2

# Method 3: Bit manipulation trick
mid = (left + right) >> 1

# Python mein left + right kabhi overflow nahi hota
# because Python integers arbitrary precision hain
# But C++/Java mein INT_MAX + INT_MAX overflow hota hai

Time Complexity kyun O(log n)?

Har step mein array aadha ho raha hai:

n = 1000 ✓ steps � 10 (log21000 � 10)
n = 1,000,000 ✓ steps � 20
n = 1,000,000,000 ✓ steps � 30

# Linear search:
n = 1000 ✓ worst case 1000 steps
n = 1,000,000 ✓ worst case 1,000,000 steps

# Binary search vs Linear Search
# 10 crore elements mein:
# Linear: 10,00,00,000 steps
# Binary: ~27 steps

Key Formula: Agar n elements hain, toh binary search mein max log2(n) + 1 steps lagenge. 32-bit integer ke liye max 32 steps. Isliye binary search almost instant hota hai!

Try it: code khud likho

Exercise

Question: Given sorted array [1, 3, 5, 6] aur target 5. Binary search se insertion position find karo (agar target hai toh uska index, nahi hai toh jahan insert hona chahiye). Answer mein index number daalo.

Question: Sorted array [1, 2, 4, 4, 4, 7, 9] mein 4 kitni baar aata hai✓ Binary search concepts use karke answer do.

Common mistakes

Infinite loop: left = mid ya right = mid likhna jab mid+1 ya mid-1 hona chahiye. Ye loop ko kabhi khatam nahi hone deta. Hamesha left = mid + 1 ya right = mid - 1 use karo jab element nahi mila.
Mid overflow: C++/Java mein (left + right) / 2 overflow de sakta hai jab dono large integers ho. Python mein ye issue nahi hai but good practice hai left + (right - left) // 2 use karna.
Sorted array nahi hai: Binary search sirf sorted arrays pe kaam karta hai! Agar array sorted nahi hai toh pehle sort karo ya linear search use karo.
Off-by-one in right: right = len(arr) vs right = len(arr) - 1. Pehla wala exclusive bound hai, doosra inclusive. Dono valid hain but loop condition alag hogi � left < right vs left <= right.

Lesson complete?

Binary Search basics samajh aa gaye✓ Ab variants dekhte hain � Lower Bound, Upper Bound, Floor/Ceil � ye sab binary search ke powerful extensions hain.