Lesson 5 � Advanced
Top Binary Search Problems
Binary Search ke 10 sabse important problems jo interview mein aate hain. Inhe solve karo toh binary search tumhara ho jayega! Har problem mein approach + code + complexity analysis hai.
10 Must-Do Problems
1. Binary Search (Basic)
Sorted array mein element dhundho. Template problem � ye sabse pehle solve karo.
2. Search Insert Position
Sorted array mein target dhundho, nahi mile toh jahan insert hona chahiye wo index return karo. Lower bound ka direct application.
3. Search in Rotated Sorted Array
Rotated sorted array mein target ka index find karo. Two cases handle karo � kaunsa half sorted hai.
4. Find Minimum in Rotated Sorted Array
Rotated array mein minimum element ka index find karo. Pivot = minimum element.
5. Koko Eating Bananas
Binary Search on Answer. Minimum speed find karo taaki Koko sab piles kha sake given hours mein.
6. Median of Two Sorted Arrays
Do sorted arrays ka median O(log(min(m,n))) mein find karo. Hard level � binary search on partition.
7. Capacity To Ship Packages
Minimum capacity find karo taaki sab packages given days mein ship ho sake. Binary Search on Answer.
8. Split Array Largest Sum
Array ko m parts mein split karo taaki maximum sum minimize ho. Binary Search on Answer.
9. Search a 2D Matrix
Row-wise aur column-wise sorted matrix mein search karo. Binary search on rows ya flattened array.
10. Find Peak Element
Array mein peak element dhundho jo apne dono neighbors se bada ho. Binary search � agar mid < mid+1 hai toh right mein jao.
Search a 2D Matrix
Ye problem binary search ka beautiful application hai:
def search_matrix(matrix, target):
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = (left + right) // 2
# 2D index nikalo 1D index se
row, col = mid // cols, mid % cols
val = matrix[row][col]
if val == target:
return True
elif val < target:
left = mid + 1
else:
right = mid - 1
return False
# Usage
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60]
]
print(search_matrix(matrix, 3)) # True
print(search_matrix(matrix, 13)) # Falsemid // cols se row nikalo, mid % cols se column nikalo. Flat binary search lagao � O(log(m*n)) time.
Find Peak Element
def find_peak_element(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
# Peak right mein hai
left = mid + 1
else:
# Peak mid ya left mein hai
right = mid
return left
# Usage
nums = [1, 2, 3, 1]
print(find_peak_element(nums)) # 2 (index of 3)
nums2 = [1, 2, 1, 3, 5, 6, 4]
print(find_peak_element(nums2)) # 5 (index of 6)Median of Two Sorted Arrays
def find_median_sorted_arrays(nums1, nums2):
# Ensure nums1 is smaller
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
x, y = len(nums1), len(nums2)
low, high = 0, x
while low <= high:
partitionX = (low + high) // 2
partitionY = (x + y + 1) // 2 - partitionX
maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
minRightX = float('inf') if partitionX == x else nums1[partitionX]
maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
minRightY = float('inf') if partitionY == y else nums2[partitionY]
if maxLeftX <= minRightY and maxLeftY <= minRightX:
if (x + y) % 2 == 0:
return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
else:
return max(maxLeftX, maxLeftY)
elif maxLeftX > minRightY:
high = partitionX - 1
else:
low = partitionX + 1
# Usage
print(find_median_sorted_arrays([1, 3], [2])) # 2.0
print(find_median_sorted_arrays([1, 2], [3, 4])) # 2.5Try it: code khud likho
Exercise
Question: Matrix = [[1,3],[5,7]]. Value 5 matrix mein hai ya nahi✓ Answer mein True ya False daalo.
Question: Array [1, 2, 1, 3, 5, 6, 4] mein peak element ka index kya hai? (Agar multiple peaks hain toh koi bhi ek do)
Common mistakes
- 2D matrix mein index mapping:
mid // colsse row aurmid % colsse column nikalte hain. Division order yaad rakho � pehle rows, phir columns. - Peak finding mein boundary:
nums[mid] < nums[mid+1]check karte waqtmid+1array ke bahar na jaaye. Isliyeleft < rightuse karo,left <= rightnahi. - Median problem mein partition logic: Ye sabse hard problem hai. PartitionX + PartitionY = (x+y+1)//2 ye formula yaad rakho. Chhote array pe binary search lagao.
- Binary Search on Answer mein range: Range hamesha realistic rakho. Jaise Koko mein min=1, max=max(piles). Empty range handle karna mat bhoolo.
Binary Search module complete! Ab Tries & Advanced topics dekhte hain � Trie, Segment Tree, Bit Manipulation aur interview patterns.