Binary Search

📋 Quick Reference

---

🎮 Interactive Visualizer

Watch how Binary Search eliminates half the search space with each comparison:

Loading visualizer...

1. Search for an element that exists - count the comparisons
2. Search for an element that doesn't exist - see where it would be
3. Notice: array of 1000 elements needs only ~10 comparisons!

---

🔧 Key Implementations

Basic Binary Search

JAVA(18 lines)
Code
Loading syntax highlighter...

Find First Occurrence (Lower Bound)

JAVA(16 lines)
Code
Loading syntax highlighter...

Find Last Occurrence (Upper Bound)

JAVA(16 lines)
Code
Loading syntax highlighter...

Java Standard Library

JAVA(10 lines)
Code
Loading syntax highlighter...

---

📊 Complexity Analysis

Why O(log n)?

Each step halves the search space:
n → n/2 → n/4 → n/8 → ... → 1

Number of steps = log₂(n)

Example: 1024 elements
1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1
= 10 steps = log₂(1024)

---

✅ When to Use Binary Search

Good Use Cases

• Searching sorted arrays - classic use case
• Finding boundaries - first/last occurrence, insertion point
• Searching in rotated arrays - modified binary search
• Finding peak elements - search space reduction
• Optimization problems - "find minimum X such that..."

Avoid When

• Unsorted data - must sort first, O(n log n)
• Small datasets - linear search is simpler for n < 10-20
• Frequent insertions - keeping array sorted is expensive
• Linked lists - no O(1) random access

---

🧩 Common Patterns

Search in Rotated Sorted Array

JAVA(28 lines)
Code
Loading syntax highlighter...

Find Peak Element

JAVA(15 lines)
Code
Loading syntax highlighter...

---

⚠️ Common Pitfalls

1. Integer Overflow

JAVA(5 lines)
Code
Loading syntax highlighter...

2. Off-by-One Errors

JAVA(17 lines)
Code
Loading syntax highlighter...

3. Forgetting Sort Requirement

JAVA(7 lines)
Code
Loading syntax highlighter...

---

🎤 Interview Tips

"

O(log n) - we eliminate half the search space with each comparison. For an array of n elements, we need at most log₂(n) + 1 comparisons.

"

Yes, the iterative version is actually preferred as it uses O(1) space vs O(log n) stack space for recursion.

"

Use lower_bound/upper_bound variants. Lower bound finds the first occurrence, upper bound finds the position after the last occurrence. Count of element = upper_bound - lower_bound.

"

For very small arrays (n < 10-20), linear search can be faster due to simpler logic and better cache behavior. Also when array is unsorted and will only be searched once.

---

📚 Series Navigation

---