[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":86,"_73":87,"_35":88},"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",36,"title","Specialized Search Algorithms","slug","algorithms-part-9-specialized-search","excerpt","Apply interpolation, exponential, jump, Fibonacci, and ternary search when data has special properties that outperform binary search.","# Algorithms Compendium Part 9: Search in Specialized Structures\n\nBinary search is optimal for sorted arrays when element distribution is unknown. But when data has special properties - uniform distribution, unbounded size, or unimodal structure - specialized algorithms can outperform binary search. This article covers five search techniques that exploit data characteristics for better performance.\n\n## 📋 At a Glance\n\n| Algorithm | Best Case | Average | Worst Case | Best For |\n|-----------|-----------|---------|------------|----------|\n| Interpolation | O(1) | O(log log n) | O(n) | Uniformly distributed data |\n| Exponential | O(1) | O(log n) | O(log n) | Unbounded/unknown size arrays |\n| Jump | O(√n) | O(√n) | O(√n) | When backward steps are expensive |\n| Fibonacci | O(log n) | O(log n) | O(log n) | When multiplication is expensive |\n| Ternary | O(log n) | O(log n) | O(log n) | Unimodal functions (find max/min) |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Apply interpolation search** when data is uniformly distributed\n- **Use exponential search** for unbounded or very large arrays\n- **Implement ternary search** for finding extrema in unimodal functions\n- **Choose the right search algorithm** based on data characteristics\n- **Recognize when specialized searches outperform binary search**\n- **Avoid common pitfalls** like applying ternary search to non-unimodal functions\n\n---\n\n## 🔥 Production Story: The Cache Key Lookup\n\nA caching system stored 10 million sorted timestamps as keys for quick range queries. Binary search worked, but a performance-critical path needed faster lookups.\n\n```java\n// ❌ Initial approach: Binary search\npublic int findTimestamp(long[] timestamps, long target) {\n return Arrays.binarySearch(timestamps, target);\n}\n// Average: ~23 comparisons (log₂(10M) ≈ 23.25)\n```\n\n**Analysis revealed:**\n- Timestamps were roughly uniformly distributed (events over 24 hours)\n- Range was known: 0 to 86,400,000 (milliseconds in a day)\n- Data was dense - few gaps in the timeline\n\n**The optimization:**\n\n```java\n// ✅ Interpolation search for uniform timestamps\npublic int findTimestampFast(long[] timestamps, long target) {\n if (timestamps.length == 0) return -1;\n\n int lo = 0, hi = timestamps.length - 1;\n long loVal = timestamps[lo];\n long hiVal = timestamps[hi];\n\n while (lo <= hi && target >= loVal && target <= hiVal) {\n if (lo == hi) {\n return timestamps[lo] == target ? lo : -1;\n }\n\n // Interpolate position based on value distribution\n // pos = lo + (target - loVal) * (hi - lo) / (hiVal - loVal)\n long range = hiVal - loVal;\n if (range == 0) break;\n\n int pos = lo + (int) ((target - loVal) * (hi - lo) / range);\n\n // Bounds check\n pos = Math.max(lo, Math.min(hi, pos));\n\n long posVal = timestamps[pos];\n\n if (posVal == target) {\n return pos;\n } else if (posVal < target) {\n lo = pos + 1;\n loVal = timestamps[lo];\n } else {\n hi = pos - 1;\n hiVal = timestamps[hi];\n }\n }\n\n return -1;\n}\n// Average: ~4 comparisons for uniform data (log log n ≈ 4.5)\n```\n\n**Results:**\n- Binary search: 23 comparisons average\n- Interpolation search: 4 comparisons average\n- **5.75x fewer comparisons** on uniform timestamp data\n\n**The lesson:** When you know data distribution, exploit it. Interpolation search trades generality for speed on uniform data.\n\n---\n\n## 🧠 Mental Model: Choosing Search Algorithms\n\n```text\nSEARCH ALGORITHM SELECTION\n━━━━━━━━━━━━━━━━━━━━━━━━━━\n\nQuestion 1: What are you searching?\n├── Sorted array → Continue\n├── Unimodal function → Ternary Search\n└── Unsorted data → Linear or Sort first\n\nQuestion 2: Is size known and bounded?\n├── Unknown/unbounded → Exponential Search\n└── Known → Continue\n\nQuestion 3: What's the data distribution?\n├── Uniform → Interpolation Search\n├── Unknown/non-uniform → Binary Search\n└── Sequential access preferred → Jump Search\n\nQuestion 4: Hardware constraints?\n├── Division expensive → Fibonacci Search\n└── Normal → Binary or above choices\n```\n\n---\n\n## 🔬 Deep Dive: Interpolation Search\n\n### The Intuition\n\nBinary search always checks the middle element. But if you're looking for \"Smith\" in a phone book, you don't open to the middle - you open closer to the back, where S names are.\n\nInterpolation search uses the same idea: estimate position based on value.\n\n```text\nINTERPOLATION VS BINARY\n━━━━━━━━━━━━━━━━━━━━━━━\n\nArray: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]\nTarget: 85\n\nBinary search:\n Iteration 1: mid = 4, arr[4] = 50 < 85 → search right\n Iteration 2: mid = 7, arr[7] = 80 < 85 → search right\n Iteration 3: mid = 8, arr[8] = 90 > 85 → search left\n Iteration 4: not found\n\nInterpolation search:\n Estimate: pos = 0 + (85 - 10) * 9 / (100 - 10) = 7.5 → 7 or 8\n Iteration 1: pos = 8, arr[8] = 90 > 85 → search left\n Iteration 2: pos = 7, arr[7] = 80 < 85 → not found (between 7 and 8)\n\nInterpolation jumps directly near the target!\n```\n\n### Implementation\n\n```java\npublic class InterpolationSearch {\n /**\n * Interpolation search for uniformly distributed sorted array.\n *\n * Time: O(log log n) average for uniform data, O(n) worst case\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 if (arr == null || arr.length == 0) return -1;\n\n int lo = 0;\n int hi = arr.length - 1;\n\n while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {\n // Handle single element remaining\n if (lo == hi) {\n return arr[lo] == target ? lo : -1;\n }\n\n // Interpolation formula\n // pos = lo + (target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo])\n int range = arr[hi] - arr[lo];\n if (range == 0) {\n // All elements equal\n return arr[lo] == target ? lo : -1;\n }\n\n // Use long to prevent overflow\n int pos = lo + (int) (((long)(target - arr[lo]) * (hi - lo)) / range);\n\n // Bounds check (defensive)\n pos = Math.max(lo, Math.min(hi, pos));\n\n if (arr[pos] == target) {\n return pos;\n } else if (arr[pos] < target) {\n lo = pos + 1;\n } else {\n hi = pos - 1;\n }\n }\n\n return -1;\n }\n\n /**\n * Interpolation search with lower bound semantics.\n * Returns first index where arr[i] >= target.\n */\n public static int lowerBound(int[] arr, int target) {\n if (arr == null || arr.length == 0) return 0;\n if (target <= arr[0]) return 0;\n if (target > arr[arr.length - 1]) return arr.length;\n\n int lo = 0;\n int hi = arr.length - 1;\n int result = arr.length;\n\n while (lo <= hi) {\n int range = arr[hi] - arr[lo];\n int pos;\n\n if (range == 0) {\n pos = lo;\n } else {\n pos = lo + (int) (((long)(target - arr[lo]) * (hi - lo)) / range);\n pos = Math.max(lo, Math.min(hi, pos));\n }\n\n if (arr[pos] >= target) {\n result = pos;\n hi = pos - 1;\n } else {\n lo = pos + 1;\n }\n }\n\n return result;\n }\n}\n```\n\n### When Interpolation Search Fails\n\n```java\n/**\n * Demonstration of interpolation search worst case.\n */\npublic class InterpolationSearchWorstCase {\n public static void main(String[] args) {\n // Exponential distribution - interpolation search degrades\n int[] exponential = new int[1000];\n for (int i = 0; i < 1000; i++) {\n exponential[i] = (int) Math.pow(2, i / 100.0);\n }\n\n // Searching for a value near the end\n // Interpolation estimates: pos ≈ 0 (because values grow exponentially)\n // Each iteration only moves forward by 1!\n\n // Binary search: ~10 iterations\n // Interpolation search: potentially hundreds of iterations!\n }\n}\n```\n\n### Interpolation Search Complexity Analysis\n\n| Data Distribution | Average Case | Worst Case |\n|-------------------|--------------|------------|\n| Uniform | O(log log n) | O(n) |\n| Linear (sorted by index) | O(1) | O(1) |\n| Exponential | O(n) | O(n) |\n| Random (non-uniform) | O(√n) to O(n) | O(n) |\n\n---\n\n## 🔬 Deep Dive: Exponential Search\n\n### The Problem\n\nBinary search requires knowing array size upfront. What if:\n- Array size is unknown (streaming/infinite)\n- Array is very large but target is likely near the beginning\n- We want to find the bounds before searching\n\n### The Algorithm\n\nExponential search finds the range where target exists, then uses binary search within that range.\n\n```text\nEXPONENTIAL SEARCH STRATEGY\n━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\nArray: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...]\nTarget: 19\n\nStep 1: Find range (exponential jumps)\n Check index 1: arr[1] = 3 < 19 → continue\n Check index 2: arr[2] = 5 < 19 → continue\n Check index 4: arr[4] = 11 < 19 → continue\n Check index 8: arr[8] = 23 > 19 → found range [4, 8]\n\nStep 2: Binary search in range [4, 8]\n mid = 6: arr[6] = 17 < 19 → search [7, 8]\n mid = 7: arr[7] = 19 = target → found!\n\nTotal: 4 exponential + 2 binary = 6 comparisons\nBinary search alone: log₂(length) comparisons\n```\n\n### Implementation\n\n```java\npublic class ExponentialSearch {\n /**\n * Exponential search - finds range then binary searches.\n *\n * Time: O(log n) always\n * Space: O(1)\n *\n * Best when target is near the beginning or array size is unknown.\n */\n public static int search(int[] arr, int target) {\n if (arr == null || arr.length == 0) return -1;\n\n // Check first element\n if (arr[0] == target) return 0;\n\n // Find range: double the bound until we exceed target\n int bound = 1;\n while (bound < arr.length && arr[bound] <= target) {\n bound *= 2;\n }\n\n // Binary search in range [bound/2, min(bound, length-1)]\n int lo = bound / 2;\n int hi = Math.min(bound, arr.length - 1);\n\n return binarySearch(arr, target, lo, hi);\n }\n\n private static int binarySearch(int[] arr, int target, int lo, int hi) {\n while (lo <= hi) {\n int mid = lo + (hi - lo) / 2;\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 return -1;\n }\n\n /**\n * Search in \"unbounded\" array (simulated with function).\n * Useful when you can only probe indices, not know size.\n */\n public static int searchUnbounded(IntUnaryOperator getElement,\n int target,\n int maxProbes) {\n // Find upper bound\n int bound = 1;\n int probes = 0;\n\n while (probes < maxProbes) {\n int value = getElement.applyAsInt(bound);\n probes++;\n\n if (value == target) return bound;\n if (value > target || value == Integer.MAX_VALUE) break; // End of array\n\n bound *= 2;\n }\n\n // Binary search\n int lo = bound / 2;\n int hi = bound;\n\n while (lo <= hi && probes < maxProbes) {\n int mid = lo + (hi - lo) / 2;\n int value = getElement.applyAsInt(mid);\n probes++;\n\n if (value == target) {\n return mid;\n } else if (value == Integer.MAX_VALUE || value > target) {\n hi = mid - 1;\n } else {\n lo = mid + 1;\n }\n }\n\n return -1;\n }\n}\n```\n\n### Use Cases\n\n```java\n/**\n * Real-world applications of exponential search.\n */\npublic class ExponentialSearchUseCases {\n\n /**\n * 1. Searching in infinite sorted stream.\n * Example: Finding a timestamp in a continuous log stream.\n */\n public int searchInStream(Iterator sortedStream, int target) {\n List buffer = new ArrayList<>();\n int bound = 1;\n\n // Exponentially read until we exceed target or stream ends\n while (sortedStream.hasNext()) {\n int value = sortedStream.next();\n buffer.add(value);\n\n if (value >= target) {\n break;\n }\n\n // Double the read amount\n for (int i = 0; i < bound && sortedStream.hasNext(); i++) {\n buffer.add(sortedStream.next());\n }\n bound *= 2;\n }\n\n // Binary search in buffer\n int idx = Collections.binarySearch(buffer, target);\n return idx >= 0 ? idx : -1;\n }\n\n /**\n * 2. Finding insertion point in large sorted file.\n * When file is large but target is likely near start.\n */\n public long findInsertionPoint(RandomAccessFile file, long target)\n throws IOException {\n long fileLength = file.length() / Long.BYTES;\n long bound = 1;\n\n // Exponential probing\n while (bound < fileLength) {\n file.seek(bound * Long.BYTES);\n if (file.readLong() >= target) break;\n bound *= 2;\n }\n\n // Binary search in [bound/2, min(bound, fileLength)]\n long lo = bound / 2;\n long hi = Math.min(bound, fileLength - 1);\n\n while (lo < hi) {\n long mid = lo + (hi - lo) / 2;\n file.seek(mid * Long.BYTES);\n if (file.readLong() < target) {\n lo = mid + 1;\n } else {\n hi = mid;\n }\n }\n\n return lo;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Ternary Search\n\n### The Concept\n\nTernary search finds the maximum or minimum of a **unimodal** function - one that increases then decreases (or vice versa).\n\n```text\nUNIMODAL FUNCTION\n━━━━━━━━━━━━━━━━━\n\n Maximum\n ●\n /|\\\n / | \\\n / | \\\n / | \\\n / | \\\n ●─────┴─────●\n f(lo) f(hi)\n\nIf f(m1) < f(m2), maximum is in [m1, hi]\nIf f(m1) > f(m2), maximum is in [lo, m2]\nIf f(m1) = f(m2), maximum is in [m1, m2]\n```\n\n### Implementation\n\n```java\npublic class TernarySearch {\n private static final double EPSILON = 1e-9;\n\n /**\n * Find x that maximizes f(x) in range [lo, hi].\n * Assumes f is unimodal (increases then decreases).\n *\n * Time: O(log n) where n = (hi - lo) / epsilon\n * Space: O(1)\n */\n public static double findMaximum(DoubleUnaryOperator f,\n double lo, double hi) {\n while (hi - lo > EPSILON) {\n double m1 = lo + (hi - lo) / 3;\n double m2 = hi - (hi - lo) / 3;\n\n if (f.applyAsDouble(m1) < f.applyAsDouble(m2)) {\n lo = m1;\n } else {\n hi = m2;\n }\n }\n\n return (lo + hi) / 2;\n }\n\n /**\n * Find x that minimizes f(x) in range [lo, hi].\n * Assumes f is unimodal (decreases then increases).\n */\n public static double findMinimum(DoubleUnaryOperator f,\n double lo, double hi) {\n while (hi - lo > EPSILON) {\n double m1 = lo + (hi - lo) / 3;\n double m2 = hi - (hi - lo) / 3;\n\n if (f.applyAsDouble(m1) > f.applyAsDouble(m2)) {\n lo = m1;\n } else {\n hi = m2;\n }\n }\n\n return (lo + hi) / 2;\n }\n\n /**\n * Discrete ternary search for arrays.\n * Find index that maximizes arr[i] where arr is unimodal.\n */\n public static int findMaxIndex(int[] arr) {\n int lo = 0, hi = arr.length - 1;\n\n while (hi - lo > 2) {\n int m1 = lo + (hi - lo) / 3;\n int m2 = hi - (hi - lo) / 3;\n\n if (arr[m1] < arr[m2]) {\n lo = m1;\n } else {\n hi = m2;\n }\n }\n\n // Linear search in remaining small range\n int maxIdx = lo;\n for (int i = lo + 1; i <= hi; i++) {\n if (arr[i] > arr[maxIdx]) {\n maxIdx = i;\n }\n }\n return maxIdx;\n }\n}\n```\n\n### Golden Section Search (Optimized Ternary)\n\nGolden section search is more efficient - it reuses one evaluation per iteration.\n\n```java\npublic class GoldenSectionSearch {\n private static final double PHI = (1 + Math.sqrt(5)) / 2; // Golden ratio\n private static final double EPSILON = 1e-9;\n\n /**\n * Golden section search - more efficient than ternary.\n * Reuses one function evaluation per iteration.\n *\n * Time: O(log n) with fewer function calls than ternary\n */\n public static double findMinimum(DoubleUnaryOperator f,\n double lo, double hi) {\n double c = hi - (hi - lo) / PHI;\n double d = lo + (hi - lo) / PHI;\n\n double fc = f.applyAsDouble(c);\n double fd = f.applyAsDouble(d);\n\n while (Math.abs(hi - lo) > EPSILON) {\n if (fc < fd) {\n hi = d;\n d = c;\n fd = fc;\n c = hi - (hi - lo) / PHI;\n fc = f.applyAsDouble(c);\n } else {\n lo = c;\n c = d;\n fc = fd;\n d = lo + (hi - lo) / PHI;\n fd = f.applyAsDouble(d);\n }\n }\n\n return (lo + hi) / 2;\n }\n}\n```\n\n### Common Applications\n\n```java\n/**\n * Ternary search applications.\n */\npublic class TernarySearchApplications {\n\n /**\n * 1. Find peak element in array (bitonic array).\n */\n public int findPeak(int[] arr) {\n return TernarySearch.findMaxIndex(arr);\n }\n\n /**\n * 2. Minimize function with single minimum.\n * Example: Find x that minimizes (x - 3)² + 5\n */\n public double findOptimalX() {\n return TernarySearch.findMinimum(\n x -> Math.pow(x - 3, 2) + 5,\n -100, 100\n ); // Returns ~3.0\n }\n\n /**\n * 3. Competitive programming: Maximum profit point.\n * Sell x items at price p(x) = 100 - 0.5x\n * Cost c(x) = x² / 10\n * Profit = x * p(x) - c(x) = x(100 - 0.5x) - x²/10\n * = 100x - 0.5x² - 0.1x² = 100x - 0.6x²\n * This is a unimodal function (parabola opening down)\n */\n public double maxProfitQuantity() {\n return TernarySearch.findMaximum(\n x -> 100 * x - 0.6 * x * x,\n 0, 200\n ); // Returns ~83.33\n }\n\n /**\n * 4. Geometry: Closest point on parabola to a given point.\n */\n public double[] closestPointOnParabola(double px, double py) {\n // Parabola: y = x²\n // Distance²: (x - px)² + (x² - py)²\n // This is unimodal in x for convex parabola\n\n double x = TernarySearch.findMinimum(\n t -> Math.pow(t - px, 2) + Math.pow(t * t - py, 2),\n -1000, 1000\n );\n\n return new double[] { x, x * x };\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Jump Search\n\n### The Concept\n\nJump search jumps ahead by fixed steps, then does linear search backward. Useful when backward movement is cheap but random access is expensive.\n\n```text\nJUMP SEARCH STRATEGY\n━━━━━━━━━━━━━━━━━━━━\n\nArray: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]\nTarget: 15\nJump size: √13 ≈ 3\n\nJump phase:\n Jump to 3: arr[3] = 7 < 15 → jump\n Jump to 6: arr[6] = 13 < 15 → jump\n Jump to 9: arr[9] = 19 > 15 → stop\n\nLinear phase (backward from 9 to 6):\n arr[8] = 17 > 15\n arr[7] = 15 = target → found!\n\nTotal: 3 jumps + 2 linear = 5 comparisons\n```\n\n### Implementation\n\n```java\npublic class JumpSearch {\n /**\n * Jump search - optimal for tape/disk storage.\n *\n * Time: O(√n)\n * Space: O(1)\n *\n * Best when backward movement is cheaper than random access\n * (e.g., magnetic tape, sequential file reading).\n */\n public static int search(int[] arr, int target) {\n if (arr == null || arr.length == 0) return -1;\n\n int n = arr.length;\n int step = (int) Math.sqrt(n); // Optimal step size\n\n // Jump phase\n int prev = 0;\n int curr = 0;\n\n while (curr < n && arr[curr] < target) {\n prev = curr;\n curr += step;\n }\n\n // Linear phase (search backward or forward in block)\n // Searching forward from prev to min(curr, n-1)\n for (int i = prev; i < Math.min(curr + 1, n); i++) {\n if (arr[i] == target) {\n return i;\n }\n if (arr[i] > target) {\n return -1;\n }\n }\n\n return -1;\n }\n\n /**\n * Jump search with custom step size.\n * Step = √n is optimal for uniform access cost.\n * Larger step if forward jumps are expensive.\n * Smaller step if backward scan is expensive.\n */\n public static int searchWithStep(int[] arr, int target, int step) {\n if (arr == null || arr.length == 0) return -1;\n\n int n = arr.length;\n int prev = 0;\n int curr = 0;\n\n while (curr < n && arr[curr] < target) {\n prev = curr;\n curr = Math.min(curr + step, n - 1);\n\n // Optimization: if we've reached the end, just search from prev\n if (curr == n - 1 && arr[curr] < target) {\n return -1;\n }\n }\n\n for (int i = prev; i <= curr; i++) {\n if (arr[i] == target) return i;\n if (arr[i] > target) return -1;\n }\n\n return -1;\n }\n}\n```\n\n### Why √n is Optimal\n\n```text\nANALYSIS OF STEP SIZE\n━━━━━━━━━━━━━━━━━━━━━\n\nLet step size = m\nNumber of jumps: n/m\nLinear search after jump: m\nTotal comparisons: n/m + m\n\nMinimize f(m) = n/m + m\nf'(m) = -n/m² + 1 = 0\nm² = n\nm = √n\n\nWith m = √n:\nTotal comparisons = √n + √n = 2√n = O(√n)\n```\n\n---\n\n## 🔬 Deep Dive: Fibonacci Search\n\n### The Concept\n\nFibonacci search divides search space using Fibonacci numbers instead of halves. Useful when multiplication/division is expensive (some embedded systems).\n\n```text\nFIBONACCI SEARCH IDEA\n━━━━━━━━━━━━━━━━━━━━━\n\nFibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, ...\nProperty: F(n) = F(n-1) + F(n-2)\n\nFor array of size ~F(n):\n - First probe at F(n-2) from start\n - If target is smaller: search first F(n-2) elements\n - If target is larger: search remaining F(n-1) elements\n\nKey insight: F(n) - F(n-2) = F(n-1) (perfect split using addition only!)\n```\n\n### Implementation\n\n```java\npublic class FibonacciSearch {\n /**\n * Fibonacci search - uses only addition/subtraction.\n *\n * Time: O(log n)\n * Space: O(1)\n *\n * Best when multiplication is expensive (specialized hardware).\n */\n public static int search(int[] arr, int target) {\n if (arr == null || arr.length == 0) return -1;\n\n int n = arr.length;\n\n // Find smallest Fibonacci number >= n\n int fib2 = 0; // F(k-2)\n int fib1 = 1; // F(k-1)\n int fib = 1; // F(k)\n\n while (fib < n) {\n fib2 = fib1;\n fib1 = fib;\n fib = fib1 + fib2;\n }\n\n // Offset for eliminated range\n int offset = -1;\n\n while (fib > 1) {\n // Check valid index\n int i = Math.min(offset + fib2, n - 1);\n\n if (arr[i] < target) {\n // Target in upper portion: F(k-1) elements\n fib = fib1;\n fib1 = fib2;\n fib2 = fib - fib1;\n offset = i;\n } else if (arr[i] > target) {\n // Target in lower portion: F(k-2) elements\n fib = fib2;\n fib1 = fib1 - fib2;\n fib2 = fib - fib1;\n } else {\n return i;\n }\n }\n\n // Check last element\n if (fib1 == 1 && offset + 1 < n && arr[offset + 1] == target) {\n return offset + 1;\n }\n\n return -1;\n }\n}\n```\n\n### When to Use Fibonacci Search\n\n| Scenario | Better Choice |\n|----------|---------------|\n| General purpose | Binary search |\n| No multiplication hardware | Fibonacci search |\n| Array much larger than cache | Fibonacci (slightly better locality) |\n| Teaching recursion patterns | Fibonacci |\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Interpolation on Non-Uniform Data\n\n```java\n// ❌ Using interpolation on exponential data\nint[] exponential = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};\ninterpolationSearch(exponential, 500);\n// Will degrade to O(n) - binary search is faster!\n\n// ✅ Check distribution before choosing algorithm\nboolean isUniform = checkUniformity(data);\nif (isUniform) {\n return interpolationSearch(data, target);\n} else {\n return Arrays.binarySearch(data, target);\n}\n```\n\n### Mistake 2: Ternary Search on Non-Unimodal Function\n\n```java\n// ❌ Ternary search on multimodal function\ndouble findMax = TernarySearch.findMaximum(\n x -> Math.sin(x), // Has many maxima!\n 0, 10\n);\n// Returns WRONG answer - could find any local maximum\n\n// ✅ Ensure function is unimodal in search range\ndouble findMax = TernarySearch.findMaximum(\n x -> Math.sin(x),\n 0, Math.PI // One maximum in [0, π]\n);\n```\n\n### Mistake 3: Jump Search with Wrong Step\n\n```java\n// ❌ Step too small - degrades to linear search\nint result = JumpSearch.searchWithStep(largeArray, target, 2);\n// Almost every comparison!\n\n// ❌ Step too large - too much linear search at end\nint result = JumpSearch.searchWithStep(largeArray, target, n);\n// Becomes linear search!\n\n// ✅ Use √n\nint step = (int) Math.sqrt(array.length);\n```\n\n### Mistake 4: Integer Overflow in Interpolation\n\n```java\n// ❌ Overflow in interpolation formula\nint pos = lo + (target - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]);\n// (target - arr[lo]) * (hi - lo) can overflow!\n\n// ✅ Use long for intermediate calculation\nint pos = lo + (int) (((long)(target - arr[lo]) * (hi - lo)) / (arr[hi] - arr[lo]));\n```\n\n---\n\n## 🐛 Debug This: The Broken Specialized Search\n\nThese implementations have bugs. Find and fix them:\n\n```java\npublic class BrokenSearch {\n\n // Bug 1: Interpolation search\n public int interpolation(int[] arr, int target) {\n int lo = 0, hi = arr.length - 1;\n\n while (lo <= hi) {\n int range = arr[hi] - arr[lo];\n int pos = lo + (target - arr[lo]) * (hi - lo) / range; // Bug\n\n if (arr[pos] == target) return pos;\n if (arr[pos] < target) lo = pos + 1;\n else hi = pos - 1;\n }\n return -1;\n }\n\n // Bug 2: Ternary search for minimum\n public double ternaryMin(DoubleUnaryOperator f, double lo, double hi) {\n while (hi - lo > 1e-9) {\n double m1 = lo + (hi - lo) / 3;\n double m2 = hi - (hi - lo) / 3;\n\n if (f.applyAsDouble(m1) < f.applyAsDouble(m2)) {\n hi = m2; // Bug\n } else {\n lo = m1; // Bug\n }\n }\n return (lo + hi) / 2;\n }\n\n // Bug 3: Exponential search\n public int exponential(int[] arr, int target) {\n int bound = 1;\n while (arr[bound] < target) { // Bug\n bound *= 2;\n }\n\n int lo = bound / 2, hi = bound; // Bug\n // Binary search...\n return -1;\n }\n}\n```\n\n

💡 Hint

\n\nLook for:\n1. Division by zero, overflow, bounds checking\n2. Logic inversion in ternary search\n3. Array bounds and target value bounds\n\n

\n\n

✅ Solution

\n\n```java\npublic class FixedSearch {\n\n // ✅ Fix 1: Interpolation with proper checks\n public int interpolation(int[] arr, int target) {\n if (arr == null || arr.length == 0) return -1;\n\n int lo = 0, hi = arr.length - 1;\n\n // ✅ Add target range check\n while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {\n // ✅ Handle single element and equal elements\n if (lo == hi) {\n return arr[lo] == target ? lo : -1;\n }\n\n int range = arr[hi] - arr[lo];\n // ✅ Prevent division by zero\n if (range == 0) {\n return arr[lo] == target ? lo : -1;\n }\n\n // ✅ Use long to prevent overflow\n int pos = lo + (int) (((long)(target - arr[lo]) * (hi - lo)) / range);\n\n // ✅ Bounds check\n pos = Math.max(lo, Math.min(hi, pos));\n\n if (arr[pos] == target) return pos;\n if (arr[pos] < target) lo = pos + 1;\n else hi = pos - 1;\n }\n return -1;\n }\n\n // ✅ Fix 2: Ternary search with correct logic for minimum\n public double ternaryMin(DoubleUnaryOperator f, double lo, double hi) {\n while (hi - lo > 1e-9) {\n double m1 = lo + (hi - lo) / 3;\n double m2 = hi - (hi - lo) / 3;\n\n // ✅ For MINIMUM: if f(m1) < f(m2), min is in [lo, m2]\n // (discard right portion where values are larger)\n if (f.applyAsDouble(m1) < f.applyAsDouble(m2)) {\n hi = m2; // Keep left part\n } else {\n lo = m1; // Keep right part\n }\n }\n return (lo + hi) / 2;\n }\n\n // ✅ Fix 3: Exponential search with bounds checking\n public int exponential(int[] arr, int target) {\n if (arr == null || arr.length == 0) return -1;\n\n // ✅ Check first element\n if (arr[0] == target) return 0;\n\n int n = arr.length;\n int bound = 1;\n\n // ✅ Bounds check AND target comparison\n while (bound < n && arr[bound] <= target) {\n bound *= 2;\n }\n\n // ✅ Correct range: [bound/2, min(bound, n-1)]\n int lo = bound / 2;\n int hi = Math.min(bound, n - 1);\n\n // Binary search in [lo, hi]\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\n return -1;\n }\n}\n```\n\n**Bugs explained:**\n\n1. **Interpolation**: Division by zero when `arr[hi] == arr[lo]`, overflow in `(target - arr[lo]) * (hi - lo)`, and missing target bounds check.\n\n2. **Ternary minimum**: The condition logic was correct, but the update was inverted. For finding minimum with unimodal (decreasing then increasing), if `f(m1) < f(m2)`, the minimum is in `[lo, m2]` not `[m1, hi]`.\n\n3. **Exponential**: Missing bounds check `bound < n` causes ArrayIndexOutOfBoundsException. Also `hi = bound` should be `hi = min(bound, n-1)`.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Adaptive Interpolation-Binary Search ⭐⭐\n\nCreate a hybrid that uses interpolation for first few iterations, then switches to binary search if not converging.\n\n```java\npublic class AdaptiveSearch {\n /**\n * Start with interpolation, switch to binary if not converging.\n */\n public int search(int[] arr, int target) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 2: Ternary Search for Bitonic Array Peak ⭐⭐\n\nFind the maximum element in a bitonic array (increases then decreases).\n\n```java\npublic class BitonicPeak {\n /**\n * Find peak in array like [1, 3, 8, 12, 4, 2].\n * Time: O(log n)\n */\n public int findPeak(int[] arr) {\n // Your implementation using ternary search\n }\n}\n```\n\n---\n\n### Exercise 3: Two-Way Exponential Search ⭐⭐⭐\n\nSearch that expands both directions from a starting point (useful when target is near a known position).\n\n```java\npublic class TwoWayExponentialSearch {\n /**\n * Search starting from index 'start', expanding both directions.\n * Useful when target is likely near 'start'.\n */\n public int search(int[] arr, int target, int start) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 4: Search in Nearly Sorted Array ⭐⭐⭐\n\nArray where each element is at most k positions from its sorted position.\n\n```java\npublic class NearlySortedSearch {\n /**\n * Search in array where elements are at most k positions away.\n * Example: k=2, [10, 3, 40, 20, 50, 80, 70]\n * Time: O(log n) with modified search\n */\n public int search(int[] arr, int target, int k) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nFor each position, check arr[mid-k] to arr[mid+k]. Combine with exponential search ideas.\n\n

\n\n---\n\n### Exercise 5: Multi-Level Interpolation Search ⭐⭐⭐⭐\n\nFor very large datasets, use hierarchical interpolation: first interpolate on a sampled summary, then search in the identified block.\n\n```java\npublic class HierarchicalSearch {\n private final int[] data;\n private final int[] samples; // Every kth element\n private final int sampleRate;\n\n /**\n * Two-level interpolation search.\n * Level 1: Interpolation on samples\n * Level 2: Interpolation/binary in identified block\n */\n public int search(int target) {\n // Your implementation\n }\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Question 1: When is interpolation search better than binary search?\n\n**Answer:**\n\nInterpolation search is better when:\n\n1. **Data is uniformly distributed**: O(log log n) vs O(log n)\n2. **Comparison is cheap but iterations are expensive**: Fewer iterations matter\n3. **Data range is known**: Can compute accurate position estimate\n\nBinary search is better when:\n\n1. **Distribution unknown or non-uniform**: Interpolation degrades to O(n)\n2. **Data is adversarial**: Binary search is always O(log n)\n3. **Simplicity matters**: Binary search is easier to implement correctly\n\n**Example numbers** for n = 1,000,000:\n- Binary search: ~20 comparisons\n- Interpolation (uniform): ~4 comparisons\n- Interpolation (exponential data): ~1,000,000 comparisons!\n\n---\n\n### Question 2: Explain when to use ternary search vs binary search\n\n**Answer:**\n\n**Binary search**: Find element in sorted array (or find boundary)\n- Input: sorted array or monotonic predicate\n- Output: position or boundary\n\n**Ternary search**: Find extremum (max/min) in unimodal function\n- Input: unimodal function\n- Output: x that maximizes/minimizes f(x)\n\n**Key difference**: Binary search works with monotonic (always increasing or always decreasing), ternary search works with unimodal (increases then decreases, or vice versa).\n\n**Cannot use binary search for**: \"Find x that maximizes f(x) where f increases then decreases\" - there's no sorted order.\n\n**Cannot use ternary search for**: \"Find 5 in sorted array\" - the array isn't unimodal, it's monotonic.\n\n---\n\n### Question 3: How would you search an infinite sorted array?\n\n**Answer:**\n\nUse exponential search:\n\n1. **Find bounds**: Start at index 1, double until arr[bound] >= target or bound exceeds array size.\n\n2. **Binary search**: Search in range [bound/2, bound].\n\n```java\npublic int searchInfinite(InfiniteArray arr, int target) {\n // Find bounds\n int bound = 1;\n while (arr.get(bound) < target) {\n bound *= 2;\n }\n\n // Binary search in [bound/2, bound]\n int lo = bound / 2, hi = bound;\n while (lo <= hi) {\n int mid = lo + (hi - lo) / 2;\n int val = arr.get(mid);\n if (val == target) return mid;\n if (val < target) lo = mid + 1;\n else hi = mid - 1;\n }\n return -1;\n}\n```\n\n**Time complexity**: O(log p) where p is target position\n- Finding bound: O(log p) iterations\n- Binary search: O(log p) iterations\n- Total: O(log p)\n\n---\n\n### Question 4: Compare jump search and binary search\n\n**Answer:**\n\n| Aspect | Jump Search | Binary Search |\n|--------|-------------|---------------|\n| Time | O(√n) | O(log n) |\n| Access pattern | Sequential forward, then backward | Random access |\n| Best for | Sequential storage (tape, disk) | Random access (RAM) |\n| Simplicity | Simpler | Slightly more complex |\n\n**When jump search wins**: Storage where sequential access is much faster than random access. On magnetic tape, jumping forward is fast but seeking to arbitrary position is slow.\n\n**Interesting fact**: For linked lists, jump search (with pointers every √n nodes) is optimal: O(√n) vs O(n) for binary search (which needs O(n) to reach middle).\n\n---\n\n### Question 5: Design a search for a sorted array where elements repeat\n\n**Answer:**\n\nFor arrays with many duplicates, consider:\n\n1. **Block-based search**: Jump by blocks, since many elements are equal.\n\n2. **Interpolation with density estimation**:\n```java\n// If many duplicates, interpolation formula needs adjustment\n// Instead of assuming uniform, model the density\ndouble density = estimateDensity(arr, lo, hi, target);\nint pos = lo + (int)((hi - lo) * density);\n```\n\n3. **Galloping/exponential for bounds**:\n```java\n// Find lower bound: gallop to find rough range\nint bound = 1;\nwhile (lo + bound < hi && arr[lo + bound] < target) {\n bound *= 2;\n}\n// Binary search in [lo + bound/2, lo + bound]\n```\n\n4. **For counting occurrences**: Use lower/upper bound (Part 8), which handles duplicates naturally.\n\n**Special case - all elements equal**: Both binary and interpolation degenerate. Need to just scan or use count information.\n\n---\n\n## 📋 Quick Reference\n\n### Algorithm Selection\n\n| Condition | Best Algorithm |\n|-----------|----------------|\n| Sorted array, general | Binary search |\n| Sorted, uniform data | Interpolation search |\n| Size unknown/unbounded | Exponential search |\n| Sequential access only | Jump search |\n| No multiplication | Fibonacci search |\n| Find max/min of unimodal | Ternary search |\n\n### Complexity Comparison\n\n| Algorithm | Best | Average | Worst | Function Calls |\n|-----------|------|---------|-------|----------------|\n| Binary | O(log n) | O(log n) | O(log n) | log₂(n) |\n| Interpolation | O(1) | O(log log n) | O(n) | varies |\n| Exponential | O(1) | O(log n) | O(log n) | 2⋅log₂(p) |\n| Jump | O(1) | O(√n) | O(√n) | 2√n |\n| Fibonacci | O(log n) | O(log n) | O(log n) | log_φ(n) |\n| Ternary | O(log n) | O(log n) | O(log n) | 2⋅log₃(n) |\n\n### Quick Formulas\n\n| Search | Position Formula |\n|--------|------------------|\n| Binary | mid = lo + (hi - lo) / 2 |\n| Interpolation | pos = lo + (target - arr[lo]) × (hi - lo) / (arr[hi] - arr[lo]) |\n| Jump | step = √n |\n| Ternary | m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3 |\n| Golden Section | m1 = hi - (hi - lo) / φ, m2 = lo + (hi - lo) / φ |\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| Day 1 | Read article, understand when to use each algorithm | 60 min |\n| Day 3 | Implement interpolation and exponential search | 30 min |\n| Day 7 | Implement ternary search, solve unimodal problems | 30 min |\n| Day 14 | Debug exercise + compare performance | 20 min |\n| Day 30 | Quiz: which algorithm for which scenario | 10 min |\n\n---\n\n## 🔗 What's Next?\n\n**Part 10: String Searching Algorithms** covers:\n- Naive approach and its limitations\n- KMP (Knuth-Morris-Pratt) algorithm\n- Rabin-Karp with rolling hash\n- Boyer-Moore for practical performance\n- Aho-Corasick for multiple patterns\n- Java's String.indexOf() internals\n\n**Key insight preview**: String searching is ubiquitous - log parsing, text editors, DNA sequencing. The right algorithm can be 10-100x faster than naive search.\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.130441Z","createdAt","2026-06-10T07:19:25.131297Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",26,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",9,"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},154,"Jump Search","jump-search",152,"Interpolation Search","interpolation-search",155,"Fibonacci","fibonacci",153,"Exponential Search","exponential-search",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]