Welcome to Day 6 of your coding interview journey.

So far, you’ve built a strong toolkit:

• ✅ Day 1: HashMaps
• ✅ Day 2: Sliding Window
• ✅ Day 3: Arrays
• ✅ Day 4: Two Pointers
• ✅ Day 5: Interval Problems

Today, we unlock one of the most powerful and high-frequency techniques:

👉 Binary Search

---

🧠 What is Binary Search?

Binary Search is an algorithm that works on sorted data and repeatedly divides the search space in half.

👉 Instead of scanning linearly (O(n)), you jump directly to the answer in:

• ⚡ O(log n) time

---

🔑 When Should You Use It?

Look for these signals:

• Sorted arrays
• “Find target” problems
• Min/Max optimization
• Search space reduction

---

⚠️ But What If the Array is Rotated?

That’s where today’s problem comes in.

---

💡 Problem – Search in Rotated Sorted Array

---

🧩 Problem

You are given a sorted array that has been rotated:

nums = [4,5,6,7,0,1,2]

👉 Find the index of a target value.

If not found, return -1.

---

❌ Brute Force

• Linear search
  👉 Time Complexity: O(n)

---

✅ Optimal Approach – Modified Binary Search

---

🧠 Key Insight

Even though the array is rotated:

👉 At least one half is always sorted

So at each step, we:

1. Find the middle
2. Check which side is sorted
3. Decide where to search next

---

🛠️ Solution in Python

def search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1

        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

---

✅ Example

nums = [4,5,6,7,0,1,2]
target = 0

print(search(nums, target))

Output:

4

---

🎯 Step-by-Step Intuition

For:

[4,5,6,7,0,1,2]

• Middle = 7
• Left side [4,5,6,7] is sorted
• Target 0 is NOT in this range
  👉 Move right

---

⚡ Complexity Analysis

• Time: O(log n)
• Space: O(1)

---

🔥 Key Pattern

👉 Identify the sorted half

This trick appears in many variations:

• Find minimum in rotated array
• Search with duplicates
• Peak element problems

---

⚠️ Common Mistakes

• ❌ Forgetting boundary conditions (<= vs <)
• ❌ Not identifying the sorted half correctly
• ❌ Infinite loops due to pointer mismanagement
• ❌ Mixing up left/right updates

---

🧪 Practice Problems

To master Binary Search, try:

1. Find minimum in rotated sorted array
2. Search insert position
3. First and last position of element
4. Peak element
5. Median of two sorted arrays

---

🎯 Key Takeaways

• Binary Search = logarithmic power
• Always think:
  • Is the data sorted?
  • Can I divide the search space?
• Learn to adapt it for:
  • Rotations
  • Conditions
  • Edge cases

---

🚀 Your Challenge (Day 6)

Solve this:

Find the minimum element in a rotated sorted array.

(Hint: use Binary Search 😉)

---

📌 Final Thoughts

Binary Search is one of the highest ROI topics in interviews.

Once you master it, you’ll unlock problems that many candidates struggle with.