[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":83,"_73":84,"_35":85},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",35,"title","Binary Search Mastery","slug","algorithms-part-8-binary-search-mastery","excerpt","Write bug-free binary search: classic, lower bound, upper bound, and equal range variants. Learn binary search on answer for parametric problems.","# Algorithms Compendium Part 8: Binary Search Mastery\n\nBinary search is deceptively simple: find an element in a sorted array in O(log n). Yet it's one of the most bug-prone algorithms - studies show that 90% of programmers cannot write a correct binary search on their first attempt. This article covers the classic algorithm, its variants, and advanced applications like \"binary search on the answer\" that appear frequently in interviews and production systems.\n\n## 📋 At a Glance\n\n| Variant | Purpose | Returns |\n|---------|---------|---------|\n| Classic | Find exact element | Index or -1 |\n| Lower bound | First element ≥ target | Insertion point |\n| Upper bound | First element > target | Insertion point |\n| Equal range | Range of equal elements | [lower, upper) |\n| Binary search on answer | Find minimum/maximum satisfying condition | Optimal value |\n\nAll variants: **O(log n)** time, **O(1)** space\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Write bug-free binary search** every time using a systematic approach\n- **Choose the right variant** (lower bound, upper bound, equal range)\n- **Apply binary search to non-array problems** (parametric search)\n- **Handle edge cases** including duplicates, rotated arrays, and 2D matrices\n- **Avoid classic bugs** like integer overflow and off-by-one errors\n- **Recognize binary search opportunities** in interview problems\n\n---\n\n## 🔥 Production Story: The Midnight Pricing Bug\n\nAn e-commerce platform used binary search to find applicable price tiers based on order quantity. During a flash sale, customers reported being charged incorrect prices.\n\n```java\n// ❌ The buggy implementation\npublic class PricingService {\n // Price tiers: [0-99: $10], [100-499: $8], [500-999: $6], [1000+: $5]\n private static final int[] TIER_THRESHOLDS = {0, 100, 500, 1000};\n private static final double[] TIER_PRICES = {10.0, 8.0, 6.0, 5.0};\n\n public double getPricePerUnit(int quantity) {\n int tierIndex = findTier(quantity);\n return TIER_PRICES[tierIndex];\n }\n\n private int findTier(int quantity) {\n int lo = 0, hi = TIER_THRESHOLDS.length - 1;\n\n while (lo < hi) {\n int mid = (lo + hi) / 2; // Bug 1: Overflow for large arrays\n if (TIER_THRESHOLDS[mid] == quantity) {\n return mid;\n } else if (TIER_THRESHOLDS[mid] < quantity) {\n lo = mid + 1; // Bug 2: Wrong for \"find tier containing quantity\"\n } else {\n hi = mid - 1;\n }\n }\n return lo;\n }\n}\n```\n\n**The bugs:**\n1. Order of 100 units returned tier 1 ($8) but should return tier 1 - correct by accident\n2. Order of 99 units returned tier 1 ($8) instead of tier 0 ($10)!\n3. Order of 500 units sometimes returned tier 1 instead of tier 2\n\n**Root cause:** The code searched for exact match, but needed to find the **last tier whose threshold ≤ quantity**.\n\n**The fix:**\n\n```java\n// ✅ Correct implementation using upper bound - 1\npublic class PricingService {\n private static final int[] TIER_THRESHOLDS = {0, 100, 500, 1000};\n private static final double[] TIER_PRICES = {10.0, 8.0, 6.0, 5.0};\n\n public double getPricePerUnit(int quantity) {\n int tierIndex = findTier(quantity);\n return TIER_PRICES[tierIndex];\n }\n\n private int findTier(int quantity) {\n // Find upper bound (first threshold > quantity), then go back one\n int lo = 0, hi = TIER_THRESHOLDS.length;\n\n while (lo < hi) {\n int mid = lo + (hi - lo) / 2; // Safe from overflow\n if (TIER_THRESHOLDS[mid] <= quantity) {\n lo = mid + 1;\n } else {\n hi = mid;\n }\n }\n\n // lo is now the first threshold > quantity\n // So lo - 1 is the tier containing quantity\n return lo - 1;\n }\n}\n\n// Test cases:\n// quantity=50 → tier 0 ($10) ✓\n// quantity=99 → tier 0 ($10) ✓\n// quantity=100 → tier 1 ($8) ✓\n// quantity=500 → tier 2 ($6) ✓\n// quantity=999 → tier 2 ($6) ✓\n// quantity=1000→ tier 3 ($5) ✓\n```\n\n**The lesson:** Binary search has many variants. Using exact-match search when you need bounds search causes subtle bugs that only manifest on boundary values.\n\n---\n\n## 🧠 Mental Model: The Binary Search Family\n\n```text\nBINARY SEARCH VARIANTS\n━━━━━━━━━━━━━━━━━━━━━━\n\nArray: [1, 2, 2, 2, 3, 4, 5]\n 0 1 2 3 4 5 6\n\nTarget: 2\n\n┌─────────────────────────────────────────────────────────────┐\n│ EXACT SEARCH │\n│ \"Find any 2\" │\n│ Result: 1, 2, or 3 (implementation-dependent) │\n│ [1, 2, 2, 2, 3, 4, 5] │\n│ ^ ^ ^ │\n└─────────────────────────────────────────────────────────────┘\n\n┌─────────────────────────────────────────────────────────────┐\n│ LOWER BOUND (bisect_left) │\n│ \"First element ≥ 2\" │\n│ Result: 1 │\n│ [1, 2, 2, 2, 3, 4, 5] │\n│ ^ │\n│ \"Where would 2 go if inserting to maintain sort, │\n│ placing it BEFORE existing 2s?\" │\n└─────────────────────────────────────────────────────────────┘\n\n┌─────────────────────────────────────────────────────────────┐\n│ UPPER BOUND (bisect_right) │\n│ \"First element > 2\" │\n│ Result: 4 │\n│ [1, 2, 2, 2, 3, 4, 5] │\n│ ^ │\n│ \"Where would 2 go if inserting to maintain sort, │\n│ placing it AFTER existing 2s?\" │\n└─────────────────────────────────────────────────────────────┘\n\n┌─────────────────────────────────────────────────────────────┐\n│ EQUAL RANGE │\n│ \"Range containing all 2s\" │\n│ Result: [1, 4) → indices 1, 2, 3 │\n│ [1, 2, 2, 2, 3, 4, 5] │\n│ ^-----^ │\n│ Count of 2s = upperBound - lowerBound = 4 - 1 = 3 │\n└─────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🔬 Deep Dive: Classic Binary Search\n\n### 🎮 Try It Yourself\n\nWatch binary search divide the search space in half with each step. Enter a target value and observe how left, mid, and right pointers converge:\n\n```visualizer-binary-search\nsize: 15\n```\n\n### The Correct Implementation\n\n```java\npublic class BinarySearch {\n /**\n * Classic binary search for exact match.\n * Time: O(log n), Space: O(1)\n *\n * @return index of target, or -1 if not found\n */\n public static int search(int[] arr, int target) {\n int lo = 0;\n int hi = arr.length - 1;\n\n while (lo <= hi) { // Note: <= not <\n int mid = lo + (hi - lo) / 2; // Prevents overflow\n\n if (arr[mid] == target) {\n return mid;\n } else if (arr[mid] < target) {\n lo = mid + 1;\n } else {\n hi = mid - 1;\n }\n }\n\n return -1; // Not found\n }\n}\n```\n\n### Why `lo + (hi - lo) / 2`?\n\n```java\n// ❌ Classic bug: Integer overflow\nint mid = (lo + hi) / 2;\n// When lo = 1_500_000_000 and hi = 2_000_000_000\n// lo + hi = 3_500_000_000 > Integer.MAX_VALUE\n// Result: negative number due to overflow!\n\n// ✅ Safe calculation\nint mid = lo + (hi - lo) / 2;\n// hi - lo is always positive and < Integer.MAX_VALUE\n// Division by 2, then add lo - safe\n\n// ✅ Alternative using unsigned shift (Java 8+)\nint mid = (lo + hi) >>> 1;\n// Unsigned right shift treats the sum as unsigned\n// Works correctly even with overflow\n```\n\n### Loop Invariant Analysis\n\n```text\nBINARY SEARCH INVARIANTS\n━━━━━━━━━━━━━━━━━━━━━━━━\n\nThroughout the loop:\n- If target exists, it's in arr[lo..hi] (inclusive)\n- arr[0..lo-1] < target (all elements before lo are smaller)\n- arr[hi+1..n-1] > target (all elements after hi are larger)\n\nLoop terminates when:\n- lo > hi: search space is empty, target not found\n- arr[mid] == target: found!\n\nExample: arr = [1, 3, 5, 7, 9], target = 5\n\nIteration 1: lo=0, hi=4, mid=2\n arr[2]=5 == target → return 2\n\nExample: arr = [1, 3, 5, 7, 9], target = 4\n\nIteration 1: lo=0, hi=4, mid=2\n arr[2]=5 > 4 → hi=1\n\nIteration 2: lo=0, hi=1, mid=0\n arr[0]=1 < 4 → lo=1\n\nIteration 3: lo=1, hi=1, mid=1\n arr[1]=3 < 4 → lo=2\n\nIteration 4: lo=2, hi=1 → lo > hi → not found\n```\n\n---\n\n## 🔬 Deep Dive: Lower Bound and Upper Bound\n\n### Lower Bound (bisect_left)\n\n```java\npublic class BinarySearchBounds {\n /**\n * Find the first index where arr[i] >= target.\n * If target > all elements, returns arr.length.\n * If target <= all elements, returns 0.\n *\n * Equivalent to: insertion point to maintain sorted order,\n * inserting BEFORE any existing equal elements.\n */\n public static int lowerBound(int[] arr, int target) {\n int lo = 0;\n int hi = arr.length; // Note: arr.length, not arr.length - 1\n\n while (lo < hi) { // Note: < not <=\n int mid = lo + (hi - lo) / 2;\n\n if (arr[mid] < target) {\n lo = mid + 1;\n } else {\n hi = mid; // Note: mid, not mid - 1\n }\n }\n\n return lo; // lo == hi at this point\n }\n}\n```\n\n### Upper Bound (bisect_right)\n\n```java\npublic class BinarySearchBounds {\n /**\n * Find the first index where arr[i] > target.\n * If target >= all elements, returns arr.length.\n * If target < all elements, returns 0.\n *\n * Equivalent to: insertion point to maintain sorted order,\n * inserting AFTER any existing equal elements.\n */\n public static int upperBound(int[] arr, int target) {\n int lo = 0;\n int hi = arr.length;\n\n while (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n\n if (arr[mid] <= target) { // Note: <= not <\n lo = mid + 1;\n } else {\n hi = mid;\n }\n }\n\n return lo;\n }\n}\n```\n\n### Equal Range\n\n```java\npublic class BinarySearchBounds {\n /**\n * Find the range [start, end) containing all occurrences of target.\n * If target not found, returns [insertionPoint, insertionPoint).\n */\n public static int[] equalRange(int[] arr, int target) {\n int lower = lowerBound(arr, target);\n int upper = upperBound(arr, target);\n return new int[] { lower, upper };\n }\n\n /**\n * Count occurrences of target in sorted array.\n */\n public static int count(int[] arr, int target) {\n int[] range = equalRange(arr, target);\n return range[1] - range[0];\n }\n\n /**\n * Check if target exists (more efficient than linear contains).\n */\n public static boolean contains(int[] arr, int target) {\n int lower = lowerBound(arr, target);\n return lower < arr.length && arr[lower] == target;\n }\n}\n```\n\n### Comparison of Variants\n\n| Variant | Condition | When lo moves | When hi moves | Returns |\n|---------|-----------|---------------|---------------|---------|\n| Exact | arr[mid] == target | arr[mid] < target | arr[mid] > target | Found index or -1 |\n| Lower bound | arr[mid] >= target | arr[mid] < target | arr[mid] >= target | First ≥ target |\n| Upper bound | arr[mid] > target | arr[mid] <= target | arr[mid] > target | First > target |\n\n---\n\n## 🔬 Deep Dive: Binary Search on Answer\n\n### The Paradigm\n\nBinary search isn't just for finding elements in arrays. It can solve any problem where:\n1. The answer space is **ordered** (monotonic)\n2. You can **verify** if a candidate answer is valid in reasonable time\n\n```text\nBINARY SEARCH ON ANSWER\n━━━━━━━━━━━━━━━━━━━━━━━\n\nTraditional: \"Is target at position mid?\"\n Array index → element comparison\n\nOn Answer: \"Is mid a valid answer?\"\n Candidate answer → validation function\n\nExample: \"Find minimum capacity to ship packages in D days\"\n\nAnswer space: [max_package_weight, sum_all_weights]\n ← smaller capacities fail larger work →\n\nBinary search finds the minimum capacity that works.\n```\n\n### Example: Minimum Ship Capacity\n\n```java\n/**\n * LeetCode 1011: Capacity to Ship Packages Within D Days\n *\n * Given package weights and D days, find minimum ship capacity\n * to ship all packages in order within D days.\n */\npublic class ShipCapacity {\n public int shipWithinDays(int[] weights, int days) {\n // Answer range: [max single package, total weight]\n int lo = 0, hi = 0;\n for (int w : weights) {\n lo = Math.max(lo, w); // Must fit largest package\n hi += w; // Could ship all in one day\n }\n\n // Binary search on answer\n while (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n\n if (canShipInDays(weights, mid, days)) {\n hi = mid; // mid works, try smaller\n } else {\n lo = mid + 1; // mid doesn't work, need larger\n }\n }\n\n return lo;\n }\n\n /**\n * Check if we can ship all packages with given capacity in given days.\n */\n private boolean canShipInDays(int[] weights, int capacity, int days) {\n int daysNeeded = 1;\n int currentLoad = 0;\n\n for (int w : weights) {\n if (currentLoad + w > capacity) {\n // Start new day\n daysNeeded++;\n currentLoad = w;\n } else {\n currentLoad += w;\n }\n }\n\n return daysNeeded <= days;\n }\n}\n```\n\n### Example: Koko Eating Bananas\n\n```java\n/**\n * LeetCode 875: Koko Eating Bananas\n *\n * Koko has H hours to eat all banana piles. Find minimum eating speed K\n * (bananas per hour) to finish in time.\n */\npublic class KokoEatingBananas {\n public int minEatingSpeed(int[] piles, int h) {\n int lo = 1; // At least 1 banana per hour\n int hi = Arrays.stream(piles).max().getAsInt(); // Max pile size\n\n while (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n\n if (canFinish(piles, mid, h)) {\n hi = mid; // mid works, try slower\n } else {\n lo = mid + 1; // mid too slow, need faster\n }\n }\n\n return lo;\n }\n\n private boolean canFinish(int[] piles, int speed, int hours) {\n long hoursNeeded = 0;\n for (int pile : piles) {\n hoursNeeded += (pile + speed - 1) / speed; // Ceiling division\n }\n return hoursNeeded <= hours;\n }\n}\n```\n\n### Example: Split Array Largest Sum\n\n```java\n/**\n * LeetCode 410: Split Array Largest Sum\n *\n * Split array into m subarrays to minimize the maximum subarray sum.\n */\npublic class SplitArrayLargestSum {\n public int splitArray(int[] nums, int m) {\n long lo = 0, hi = 0;\n for (int num : nums) {\n lo = Math.max(lo, num); // At least max element\n hi += num; // At most sum of all\n }\n\n while (lo < hi) {\n long mid = lo + (hi - lo) / 2;\n\n if (canSplit(nums, m, mid)) {\n hi = mid; // Can do with this max, try smaller\n } else {\n lo = mid + 1; // Can't do, need larger max\n }\n }\n\n return (int) lo;\n }\n\n private boolean canSplit(int[] nums, int m, long maxSum) {\n int splits = 1;\n long currentSum = 0;\n\n for (int num : nums) {\n if (currentSum + num > maxSum) {\n splits++;\n currentSum = num;\n } else {\n currentSum += num;\n }\n }\n\n return splits <= m;\n }\n}\n```\n\n### Recognizing Binary Search on Answer Problems\n\n| Pattern | Example Problem |\n|---------|-----------------|\n| \"Minimize the maximum...\" | Split array largest sum |\n| \"Maximize the minimum...\" | Magnetic force between balls |\n| \"Find minimum X such that...\" | Ship capacity, eating speed |\n| \"Find maximum X such that...\" | Maximum candies allocated |\n| Monotonic feasibility | If X works, X+1 also works (or vice versa) |\n\n---\n\n## 🔬 Deep Dive: Rotated Sorted Array\n\n### Finding Element in Rotated Array\n\n```java\n/**\n * Search in rotated sorted array (no duplicates).\n * Array was sorted, then rotated at some pivot.\n * Example: [4, 5, 6, 7, 0, 1, 2] (rotated at index 4)\n */\npublic class RotatedArraySearch {\n public int search(int[] nums, int target) {\n int lo = 0, hi = nums.length - 1;\n\n while (lo <= hi) {\n int mid = lo + (hi - lo) / 2;\n\n if (nums[mid] == target) {\n return mid;\n }\n\n // Determine which half is sorted\n if (nums[lo] <= nums[mid]) {\n // Left half is sorted\n if (nums[lo] <= target && target < nums[mid]) {\n hi = mid - 1; // Target in left half\n } else {\n lo = mid + 1; // Target in right half\n }\n } else {\n // Right half is sorted\n if (nums[mid] < target && target <= nums[hi]) {\n lo = mid + 1; // Target in right half\n } else {\n hi = mid - 1; // Target in left half\n }\n }\n }\n\n return -1;\n }\n}\n```\n\n### Finding Minimum in Rotated Array\n\n```java\n/**\n * Find minimum element in rotated sorted array (no duplicates).\n */\npublic class RotatedArrayMinimum {\n public int findMin(int[] nums) {\n int lo = 0, hi = nums.length - 1;\n\n // If not rotated (or rotated by full length)\n if (nums[lo] < nums[hi]) {\n return nums[lo];\n }\n\n while (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n\n if (nums[mid] > nums[hi]) {\n // Minimum is in right half\n lo = mid + 1;\n } else {\n // Minimum is in left half (including mid)\n hi = mid;\n }\n }\n\n return nums[lo];\n }\n}\n```\n\n### Handling Duplicates\n\n```java\n/**\n * Search in rotated sorted array with duplicates.\n * Worst case: O(n) when all elements are equal except one.\n */\npublic class RotatedArrayWithDuplicates {\n public boolean search(int[] nums, int target) {\n int lo = 0, hi = nums.length - 1;\n\n while (lo <= hi) {\n int mid = lo + (hi - lo) / 2;\n\n if (nums[mid] == target) {\n return true;\n }\n\n // Handle duplicates: can't determine sorted half\n if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {\n lo++;\n hi--;\n continue;\n }\n\n if (nums[lo] <= nums[mid]) {\n // Left half is sorted\n if (nums[lo] <= target && target < nums[mid]) {\n hi = mid - 1;\n } else {\n lo = mid + 1;\n }\n } else {\n // Right half is sorted\n if (nums[mid] < target && target <= nums[hi]) {\n lo = mid + 1;\n } else {\n hi = mid - 1;\n }\n }\n }\n\n return false;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: 2D Matrix Search\n\n### Row-Column Sorted Matrix\n\n```java\n/**\n * Search in matrix where each row and each column is sorted.\n * (Elements are not globally sorted)\n *\n * Example:\n * [1, 4, 7, 11]\n * [2, 5, 8, 12]\n * [3, 6, 9, 16]\n * [10, 13, 14, 17]\n *\n * Time: O(m + n), not O(log(mn))!\n */\npublic class SearchMatrix2D {\n public boolean searchMatrix(int[][] matrix, int target) {\n if (matrix == null || matrix.length == 0) return false;\n\n int rows = matrix.length;\n int cols = matrix[0].length;\n\n // Start from top-right corner\n int row = 0, col = cols - 1;\n\n while (row < rows && col >= 0) {\n if (matrix[row][col] == target) {\n return true;\n } else if (matrix[row][col] > target) {\n col--; // Target must be in left columns\n } else {\n row++; // Target must be in lower rows\n }\n }\n\n return false;\n }\n}\n```\n\n### Fully Sorted Matrix\n\n```java\n/**\n * Search in matrix where elements are sorted row-wise\n * AND the first element of each row > last element of previous row.\n * (Matrix is essentially a sorted 1D array in row-major order)\n *\n * Example:\n * [1, 3, 5, 7]\n * [10, 11, 16, 20]\n * [23, 30, 34, 60]\n *\n * Time: O(log(m × n))\n */\npublic class SearchSortedMatrix {\n public boolean searchMatrix(int[][] matrix, int target) {\n if (matrix == null || matrix.length == 0) return false;\n\n int rows = matrix.length;\n int cols = matrix[0].length;\n\n // Treat as 1D array\n int lo = 0, hi = rows * cols - 1;\n\n while (lo <= hi) {\n int mid = lo + (hi - lo) / 2;\n int row = mid / cols;\n int col = mid % cols;\n\n if (matrix[row][col] == target) {\n return true;\n } else if (matrix[row][col] < target) {\n lo = mid + 1;\n } else {\n hi = mid - 1;\n }\n }\n\n return false;\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Integer Overflow in Mid Calculation\n\n```java\n// ❌ Overflows when lo + hi > Integer.MAX_VALUE\nint mid = (lo + hi) / 2;\n\n// ✅ Safe alternatives\nint mid = lo + (hi - lo) / 2;\nint mid = (lo + hi) >>> 1; // Unsigned right shift\n```\n\n### Mistake 2: Wrong Loop Condition\n\n```java\n// ❌ For exact search, this exits too early\nwhile (lo < hi) { ... }\n\n// ✅ For exact search, use <=\nwhile (lo <= hi) { ... }\n\n// ❌ For bound search with hi = arr.length, this loops forever\nwhile (lo <= hi) { ... }\n\n// ✅ For bound search with hi = arr.length\nwhile (lo < hi) { ... }\n```\n\n### Mistake 3: Off-by-One in Bound Updates\n\n```java\n// ❌ Infinite loop when lo = mid\nlo = mid; // If mid = lo, this doesn't progress!\n\n// ✅ Always move by at least 1\nlo = mid + 1;\n\n// ❌ For lower bound, this skips potential answer\nhi = mid - 1;\n\n// ✅ For lower bound, keep mid in range\nhi = mid;\n```\n\n### Mistake 4: Wrong Condition in Bounds Search\n\n```java\n// ❌ For lower bound (first >= target)\nif (arr[mid] <= target) { // Wrong: should be <\n lo = mid + 1;\n}\n\n// ✅ For lower bound\nif (arr[mid] < target) { // Correct\n lo = mid + 1;\n}\n```\n\n### Mistake 5: Not Handling Empty Array\n\n```java\n// ❌ ArrayIndexOutOfBoundsException on empty array\npublic int search(int[] arr, int target) {\n int lo = 0, hi = arr.length - 1; // hi = -1 for empty array!\n int mid = lo + (hi - lo) / 2; // mid = -1!\n if (arr[mid] == target) ... // Crash!\n}\n\n// ✅ Handle empty array\npublic int search(int[] arr, int target) {\n if (arr == null || arr.length == 0) return -1;\n // ...\n}\n```\n\n---\n\n## 🐛 Debug This: The Buggy Binary Search Collection\n\nThese binary search implementations have bugs. Find and fix them:\n\n```java\npublic class BuggyBinarySearch {\n\n // Bug 1: Find target in sorted array\n public int search(int[] arr, int target) {\n int lo = 0, hi = arr.length; // Bug here\n\n while (lo < hi) {\n int mid = (lo + hi) / 2;\n if (arr[mid] == target) {\n return mid;\n } else if (arr[mid] < target) {\n lo = mid; // Bug here\n } else {\n hi = mid;\n }\n }\n return -1;\n }\n\n // Bug 2: Find first occurrence of target\n public int firstOccurrence(int[] arr, int target) {\n int lo = 0, hi = arr.length - 1;\n\n while (lo <= hi) {\n int mid = lo + (hi - lo) / 2;\n if (arr[mid] == target) {\n hi = mid; // Bug here\n } else if (arr[mid] < target) {\n lo = mid + 1;\n } else {\n hi = mid - 1;\n }\n }\n return lo < arr.length && arr[lo] == target ? lo : -1;\n }\n\n // Bug 3: Binary search on answer - find square root\n public int sqrt(int x) {\n if (x < 2) return x;\n\n int lo = 1, hi = x / 2;\n\n while (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n if (mid * mid <= x) { // Bug here\n lo = mid + 1;\n } else {\n hi = mid - 1;\n }\n }\n return lo;\n }\n}\n```\n\n

💡 Hint

\n\nLook for:\n1. Inclusive vs exclusive bounds consistency\n2. Infinite loop conditions\n3. Off-by-one errors in first occurrence\n4. Integer overflow in multiplication\n5. Returning lo vs lo-1\n\n

\n\n

✅ Solution

\n\n```java\npublic class FixedBinarySearch {\n\n // ✅ Fix 1: Exact search with proper bounds\n public int search(int[] arr, int target) {\n if (arr == null || arr.length == 0) return -1;\n\n int lo = 0, hi = arr.length - 1; // ✅ Use length - 1 for exact search\n\n while (lo <= hi) { // ✅ Use <= for exact search\n int mid = lo + (hi - lo) / 2; // ✅ Avoid overflow\n if (arr[mid] == target) {\n return mid;\n } else if (arr[mid] < target) {\n lo = mid + 1; // ✅ Always move forward\n } else {\n hi = mid - 1; // ✅ For exact search, can exclude mid\n }\n }\n return -1;\n }\n\n // ✅ Fix 2: First occurrence using proper lower bound\n public int firstOccurrence(int[] arr, int target) {\n if (arr == null || arr.length == 0) return -1;\n\n int lo = 0, hi = arr.length; // ✅ hi = length for lower bound\n\n while (lo < hi) { // ✅ Use < for bound search\n int mid = lo + (hi - lo) / 2;\n if (arr[mid] < target) {\n lo = mid + 1;\n } else {\n hi = mid; // ✅ Include mid in range when arr[mid] >= target\n }\n }\n\n // ✅ Check if we actually found the target\n return lo < arr.length && arr[lo] == target ? lo : -1;\n }\n\n // ✅ Fix 3: Integer square root with overflow protection\n public int sqrt(int x) {\n if (x < 2) return x;\n\n int lo = 1, hi = x / 2 + 1; // ✅ +1 to handle x = 4, etc.\n\n while (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n\n // ✅ Use division to avoid overflow: mid * mid <= x ↔ mid <= x / mid\n if (mid <= x / mid) {\n lo = mid + 1;\n } else {\n hi = mid;\n }\n }\n\n return lo - 1; // ✅ Return lo - 1 (last valid value)\n }\n}\n```\n\n**Bugs explained:**\n\n1. **search()**: Using `hi = length` with `while (lo < hi)` but treating it as exact search. Also `lo = mid` causes infinite loop. Mixed paradigms.\n\n2. **firstOccurrence()**: Using `while (lo <= hi)` with `hi = mid` causes infinite loop when `lo == hi == mid` and `arr[mid] == target`.\n\n3. **sqrt()**: `mid * mid` overflows for large x. Also, the logic for finding floor(sqrt) was inverted.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Find Peak Element ⭐\n\nFind a peak element in array where `arr[i] ≠ arr[i+1]`. A peak is greater than neighbors.\n\n```java\npublic class FindPeak {\n /**\n * Find index of any peak element.\n * Peak: arr[i-1] < arr[i] > arr[i+1]\n * Edges: arr[0] > arr[1] or arr[n-2] < arr[n-1]\n * Time: O(log n)\n */\n public int findPeakElement(int[] nums) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nIf arr[mid] < arr[mid+1], a peak must exist to the right. Otherwise, a peak exists to the left (or at mid).\n\n

\n\n---\n\n### Exercise 2: Search in 2D Matrix (Arbitrary Sorted) ⭐⭐\n\nMatrix where rows are sorted left-to-right, columns are sorted top-to-bottom (but row end may be less than next row start).\n\n```java\npublic class Search2DMatrix {\n /**\n * Time: O(m + n) - not O(log(mn))\n */\n public boolean searchMatrix(int[][] matrix, int target) {\n // Your implementation using staircase search\n }\n}\n```\n\n---\n\n### Exercise 3: Find Minimum in Rotated Array II ⭐⭐⭐\n\nFind minimum in rotated sorted array that may contain duplicates.\n\n```java\npublic class FindMinRotatedWithDuplicates {\n /**\n * Time: O(log n) average, O(n) worst case (all duplicates)\n */\n public int findMin(int[] nums) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 4: Aggressive Cows (Binary Search on Answer) ⭐⭐⭐\n\nPlace C cows in N stalls at positions x₁, x₂, ..., xₙ. Maximize minimum distance between any two cows.\n\n```java\npublic class AggressiveCows {\n /**\n * @param stalls Positions of stalls (unsorted)\n * @param cows Number of cows to place\n * @return Maximum possible minimum distance\n */\n public int maxMinDistance(int[] stalls, int cows) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nBinary search on the answer (minimum distance). For each candidate distance D, check if you can place all cows with at least D distance apart using greedy placement.\n\n

\n\n---\n\n### Exercise 5: Median of Two Sorted Arrays ⭐⭐⭐⭐\n\nFind median of two sorted arrays in O(log(min(m,n))) time.\n\n```java\npublic class MedianTwoSortedArrays {\n /**\n * Time: O(log(min(m, n)))\n * Space: O(1)\n */\n public double findMedianSortedArrays(int[] nums1, int[] nums2) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nBinary search on partition point of smaller array. If we partition both arrays such that left halves have (m+n+1)/2 elements total, median is derived from elements around partition.\n\n

\n\n---\n\n## 🎤 Interview Questions\n\n### Question 1: Why is binary search often implemented incorrectly?\n\n**Answer:**\n\nBinary search is tricky because of several interdependent decisions:\n\n1. **Bounds: inclusive vs exclusive?**\n - `hi = arr.length - 1` (inclusive) vs `hi = arr.length` (exclusive)\n - Must be consistent throughout\n\n2. **Loop condition: < or <=?**\n - `while (lo < hi)` for bounds search (hi = length)\n - `while (lo <= hi)` for exact search (hi = length - 1)\n\n3. **Update rules: mid or mid±1?**\n - Must ensure progress (no infinite loops)\n - Must not skip potential answers\n\n4. **Different variants need different logic**\n - Exact search, lower bound, upper bound all differ\n\n**The fix:** Use templates. Memorize one correct implementation for each variant and always use it.\n\n---\n\n### Question 2: When would you use binary search over hash table lookup?\n\n**Answer:**\n\nUse binary search when:\n\n1. **Memory constrained**: Binary search is O(1) space, hash table is O(n)\n\n2. **Range queries needed**: \"Find all elements between A and B\" - binary search gives O(log n + k), hash table is O(n)\n\n3. **Ordered iteration needed**: Binary search maintains order, hash tables don't\n\n4. **Predecessor/successor queries**: \"Find largest element ≤ X\" - O(log n) with binary search, O(n) with hash table\n\n5. **Data is already sorted**: No preprocessing needed\n\nUse hash table when:\n\n1. **Exact lookup only**: O(1) average vs O(log n)\n2. **Frequent insertions/deletions**: Hash table is O(1), maintaining sorted array is O(n)\n3. **Memory is plentiful**: Hash table's O(1) lookup is hard to beat\n\n---\n\n### Question 3: Explain binary search on answer with an example\n\n**Answer:**\n\nBinary search on answer finds optimal value when:\n1. Answer space is ordered\n2. There's a monotonic feasibility function\n\n**Example: Minimum pages allocation**\n\nProblem: N books with pages[i]. Allocate to K students such that maximum pages assigned to any student is minimized. Each student gets contiguous books.\n\n```java\npublic int minMaxPages(int[] pages, int k) {\n // Answer range: [max single book, sum all books]\n int lo = Arrays.stream(pages).max().getAsInt();\n int hi = Arrays.stream(pages).sum();\n\n while (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n\n // Can we allocate with max = mid?\n if (canAllocate(pages, k, mid)) {\n hi = mid; // Try smaller max\n } else {\n lo = mid + 1; // Need larger max\n }\n }\n return lo;\n}\n\nboolean canAllocate(int[] pages, int k, int maxPages) {\n int students = 1, currentPages = 0;\n for (int p : pages) {\n if (currentPages + p > maxPages) {\n students++;\n currentPages = p;\n } else {\n currentPages += p;\n }\n }\n return students <= k;\n}\n```\n\nThe key insight: if we can allocate with max=X, we can also allocate with max=X+1. This monotonicity enables binary search.\n\n---\n\n### Question 4: How would you handle duplicates in binary search?\n\n**Answer:**\n\nDuplicates affect what \"find\" means:\n\n1. **Find any occurrence**: Standard binary search works (returns any matching index)\n\n2. **Find first occurrence (lower bound)**:\n```java\nwhile (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n if (arr[mid] < target) lo = mid + 1;\n else hi = mid; // Keep searching left even if equal\n}\n```\n\n3. **Find last occurrence**:\n```java\nwhile (lo < hi) {\n int mid = lo + (hi - lo + 1) / 2; // Round up!\n if (arr[mid] <= target) lo = mid; // Keep searching right\n else hi = mid - 1;\n}\n```\n\n4. **Count occurrences**: `upperBound - lowerBound`\n\n5. **Rotated array with duplicates**: Worst case becomes O(n) because can't determine which half is sorted when `arr[lo] == arr[mid] == arr[hi]`.\n\n---\n\n### Question 5: Compare iterative vs recursive binary search\n\n**Answer:**\n\n| Aspect | Iterative | Recursive |\n|--------|-----------|-----------|\n| Space | O(1) | O(log n) stack |\n| Performance | Slightly faster (no call overhead) | Slightly slower |\n| Readability | More explicit | More elegant |\n| Tail recursion | N/A | Could be optimized (not in Java) |\n| Debugging | Easier (can inspect lo, hi) | Harder (stack frames) |\n\n**Recommendation**: Use iterative in production (O(1) space, no stack overflow risk). Use recursive when teaching or when algorithm naturally recursive.\n\n```java\n// Iterative - preferred\npublic int searchIterative(int[] arr, int target) {\n int lo = 0, hi = arr.length - 1;\n while (lo <= hi) {\n int mid = lo + (hi - lo) / 2;\n if (arr[mid] == target) return mid;\n if (arr[mid] < target) lo = mid + 1;\n else hi = mid - 1;\n }\n return -1;\n}\n\n// Recursive - elegant but uses stack\npublic int searchRecursive(int[] arr, int target, int lo, int hi) {\n if (lo > hi) return -1;\n int mid = lo + (hi - lo) / 2;\n if (arr[mid] == target) return mid;\n if (arr[mid] < target)\n return searchRecursive(arr, target, mid + 1, hi);\n return searchRecursive(arr, target, lo, mid - 1);\n}\n```\n\n---\n\n## 📋 Quick Reference\n\n### Binary Search Templates\n\n**Template 1: Exact Search**\n```java\nint lo = 0, hi = arr.length - 1;\nwhile (lo <= hi) {\n int mid = lo + (hi - lo) / 2;\n if (arr[mid] == target) return mid;\n if (arr[mid] < target) lo = mid + 1;\n else hi = mid - 1;\n}\nreturn -1;\n```\n\n**Template 2: Lower Bound (First ≥ target)**\n```java\nint lo = 0, hi = arr.length;\nwhile (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n if (arr[mid] < target) lo = mid + 1;\n else hi = mid;\n}\nreturn lo; // First index where arr[i] >= target\n```\n\n**Template 3: Upper Bound (First > target)**\n```java\nint lo = 0, hi = arr.length;\nwhile (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n if (arr[mid] <= target) lo = mid + 1;\n else hi = mid;\n}\nreturn lo; // First index where arr[i] > target\n```\n\n**Template 4: Binary Search on Answer**\n```java\nint lo = minPossible, hi = maxPossible;\nwhile (lo < hi) {\n int mid = lo + (hi - lo) / 2;\n if (isValid(mid)) hi = mid; // mid works, try smaller\n else lo = mid + 1; // mid fails, need larger\n}\nreturn lo; // Minimum valid answer\n```\n\n### Common Patterns\n\n| Pattern | Recognize By | Template |\n|---------|--------------|----------|\n| Find element | \"Find X in sorted array\" | Exact search |\n| Find position | \"Where would X be inserted?\" | Lower/upper bound |\n| Find first/last | \"First occurrence of X\" | Modified bounds |\n| Find optimal | \"Minimum capacity such that...\" | Search on answer |\n| Rotated array | \"Sorted then rotated\" | Two-phase analysis |\n\n### Java Standard Library\n\n```java\n// Arrays.binarySearch - returns index or (-(insertion point) - 1)\nint idx = Arrays.binarySearch(arr, target);\nif (idx < 0) {\n int insertionPoint = -idx - 1;\n}\n\n// Collections.binarySearch - same behavior for Lists\nint idx = Collections.binarySearch(list, target);\n\n// TreeSet/TreeMap - O(log n) operations\nTreeSet set = new TreeSet<>();\nset.ceiling(x); // Smallest element >= x\nset.floor(x); // Largest element <= x\nset.higher(x); // Smallest element > x\nset.lower(x); // Largest element < x\n```\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| Day 1 | Read full article, understand all templates | 60 min |\n| Day 3 | Implement exact, lower bound, upper bound from scratch | 30 min |\n| Day 7 | Solve 3 \"binary search on answer\" problems | 45 min |\n| Day 14 | Solve rotated array variants | 30 min |\n| Day 30 | Mock interview: explain and implement | 20 min |\n\n---\n\n## 🔗 What's Next?\n\n**Part 9: Search in Specialized Structures** covers:\n- Ternary search for unimodal functions\n- Interpolation search for uniform distributions\n- Exponential search for unbounded arrays\n- Fibonacci search\n- Jump search\n\n**Key insight preview**: When data has known distribution or special properties, we can beat O(log n) with smarter search strategies.\n\n---\n\n*This article is part of the Algorithms Compendium series. For the complete learning path, see Part 0: How to Use This Series.*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.116449Z","createdAt","2026-06-10T07:19:25.117236Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",26,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",8,"author",{"_31":55,"_99":57,"_100":101,"_102":103,"_104":-5,"_105":-5,"_106":-5,"_107":-5,"_108":-5},"category",{"_31":95,"_73":59,"_35":96,"_76":97,"_98":-5},"tags",[79,80,81,82],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":92,"_73":93,"_35":94},{"_31":89,"_73":90,"_35":91},{"_31":86,"_73":87,"_35":88},{"_31":83,"_73":84,"_35":85},150,"Upper Bound","upper-bound",151,"Parametric Search","parametric-search",149,"Lower Bound","lower-bound",148,"Binary Search","binary-search",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]