Binary Search Basic
Mahabharata — Arjuna's Oracle — Finding the Target in a Sorted Army
व्यवस्थिते सैन्ये — अर्धे अर्धे विभज्य। लक्ष्यं प्रत्येकस्मिन् विभागे — तावत् यावत् मिलेत्॥
*In a sorted army — divide into half and half. Check the target in each half — repeat until found.*
The Story
Given a sorted array and a target, return the target's index (or -1 if not found).
For `nums = [-1,0,3,5,9,12]`, target=9: return index 4.
Arjuna stood before a perfectly sorted formation of warriors (small to large). He needed to find warrior number 9.
"I could scan from left to right," Arjuna thought. "But this army is SORTED. I can use binary search."
**The core algorithm:** ``` left=0, right=n-1 while left <= right: mid = left + (right-left)/2 // Avoids integer overflow if nums[mid] == target: return mid if nums[mid] < target: left = mid+1 // Target is in right half else: right = mid-1 // Target is in left half return -1 // Not found ```
Trace `[-1,0,3,5,9,12]`, target=9: - left=0, right=5, mid=2, nums[2]=3 < 9 → left=3 - left=3, right=5, mid=4, nums[4]=9 == 9 → return 4 ✓
**The critical details:** 1. `mid = left + (right-left)/2` not `(left+right)/2` → avoids integer overflow 2. `left <= right` (with `=`) → handles single-element arrays 3. `left = mid+1` and `right = mid-1` (not mid) → avoids infinite loops
**Why O(log n)?** Each iteration halves the search space. Starting from n, after log₂n steps, the search space is 1.
The Linear Scan
Scan from left to right. Return index when target found. O(n). Doesn't exploit sorted order.
public int searchBruteForce(int[] nums, int target) {
for (int i = 0; i < nums.length; i++)
if (nums[i] == target) return i;
return -1;
}Arjuna's Halving Wisdom
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Step-by-Step Walkthrough
nums=[5], target=5 l=0,r=0,mid=0,arr[0]=5==5 → return 0 ✅ nums=[5], target=3 l=0,r=0,mid=0,arr[0]=5>3 → r=-1 l=0>r=-1 → return -1 ✅
Deep Insight
**Integer overflow prevention:** `(left+right)/2` overflows when both are large ints (≥1B each). `left + (right-left)/2` is mathematically identical but safe.
**The `<=` in while condition:** When left==right, we still need to check that single element. Missing this case causes bugs with single-element arrays.
**`mid+1` / `mid-1`:** After checking that nums[mid] is NOT the target, we correctly exclude mid from future searches. Using just `mid` would cause an infinite loop when left==right.
**This is the foundation of the entire Binary Search pattern.** All other binary search problems (bs-2 through bs-23) are variations on this template — finding the right search condition and which half to eliminate.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Linear scan |
| Optimal | O(log n) | O(1) | Halves search space each iteration |
Pattern Recognition
✅ Sorted array + target → binary search ✅ left=0, right=n-1, while left<=right ✅ mid=left+(right-left)/2 ✅ Adjust bounds by mid±1 (not mid) **LeetCode Trigger Phrases:** → "sorted array" + find target → "O(log n)" time required → Foundation for all binary search variants
Bhagavad Gita 1.21
अर्जुन उवाच: सेनयोरुभयोर्मध्ये रथं स्थापय मेऽच्युत। यावदेतान्निरीक्षेऽहं योद्धुकामानवस्थितान्॥
Arjuna said: O Achyuta, please place my chariot between the two armies so that I may observe those who stand here eager to fight.
Connection: Binary search positions itself at the midpoint — between the two armies of possibilities — and observes. From this middle vantage point, it immediately determines which half the target belongs to, discarding the other half entirely. Like Arjuna who, placed at the center, gains complete perspective of the battlefield before deciding his course, the algorithm's power comes from its central position that reveals the structure of the sorted search space.