🚀 DSA Sheet – Day 8: Binary Search

Binary Search is not just about searching — it’s about optimizing decisions. This section covers classic problems and “Binary Search on Answer” patterns used in top interviews.

📊 Progress Tracker

Progress: 0 / 7 Completed

Done	Problem	Practice	Level	Companies
	Peak Index in Mountain Array	Solve	Medium	Google, TCS
	Search in Rotated Sorted Array	Solve	Medium	Flipkart, Hike
	Single Element in Sorted Array	Solve	Medium	TCS, Infosys
	Aggressive Cows	Solve	Medium	Adobe
	Allocate Minimum Pages	Solve	Medium	Amazon, Google
	Painter's Partition	Solve	Medium	Google, Microsoft
	Median of Two Sorted Arrays	Solve	Hard	Amazon, Google

🧠 Key Approaches

• Peak Index: Binary search using slope (increasing/decreasing)
• Rotated Array: Identify sorted half and eliminate search space
• Single Element: Use index parity (even/odd trick)
• Aggressive Cows: Binary search on answer (distance)
• Allocate Pages: Binary search on answer (max pages)
• Painter’s Partition: Same pattern as allocation problems
• Median of Arrays: Binary search on partitions

⚡ Quick Cheatsheet

Search in Rotated Sorted Array

while(l <= r){
  int mid = (l + r) / 2;

  if(nums[mid] == target) return mid;

  if(nums[l] <= nums[mid]){
    if(target >= nums[l] && target < nums[mid]) 
      r = mid - 1;
    else 
      l = mid + 1;
  } else {
    if(target > nums[mid] && target <= nums[r]) 
      l = mid + 1;
    else 
      r = mid - 1;
  }
}
    

Binary Search on Answer

while(low <= high){
  int mid = (low + high) / 2;

  if(isPossible(mid)) 
    high = mid - 1;
  else 
    low = mid + 1;
}
    

Median of Two Sorted Arrays (Partition Logic)

int cut1 = (l + r) / 2;
int cut2 = (n1 + n2 + 1) / 2 - cut1;
    

🔥 Pro Tip

Binary Search is a mindset:

• Always think in terms of search space
• Look for monotonic conditions
• Use Binary Search on Answer when brute force is O(n²)

Once you master this, you’ll start solving “hard” problems efficiently.

🏠 All Days ⬅ Previous Next ➡