Definition
- Search insert position – a binary search that returns the index if the target is found, or the lower-bound insertion index if it is not.
- Return low – when the loop terminates without a match, the
lowpointer naturally rests at the correct insertion point. - Loop invariant – everything before
lowis strictly less than the target; everything fromhigh + 1onward is strictly greater. - Lower-bound primitive – this is the building block for inserting into sorted structures and counting elements below a value.
- O(log n) time, O(1) space – identical complexity to standard binary search.
The National Bank of India keeps interest-rate tiers sorted in ascending order. When a new rate comes in, the clerk must slot it into the correct position so the list stays sorted. He binary-searches for the rate; if it already exists he returns that slot, and if not, the search naturally stops at the exact gap where the new rate belongs.
Understanding the Concepts
What is the search insert position problem?
Given a sorted array of distinct integers and a target value, return the index of the target if it exists, or the index where it would be inserted to maintain sorted order. The solution must run in O(log n) time.
This is standard binary search with one change: instead of returning -1 on failure, you return the value of low.
package com.bank.search;
public class SearchInsertPosition {
public static int searchInsert(int[] rates, int target) {
int low = 0, high = rates.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (rates[mid] == target) return mid;
if (rates[mid] < target) low = mid + 1;
else high = mid - 1;
}
return low; // insertion point
}
public static void main(String[] args) {
int[] interestRates = {200, 400, 600, 800, 1000}; // basis points
System.out.println("Insert 500 at: " + searchInsert(interestRates, 500));
System.out.println("Find 600 at: " + searchInsert(interestRates, 600));
System.out.println("Insert 100 at: " + searchInsert(interestRates, 100));
System.out.println("Insert 1200 at: " + searchInsert(interestRates, 1200));
}
}
Insert 500 at: 2
Find 600 at: 2
Insert 100 at: 0
Insert 1200 at: 5
Why does returning low give the correct insertion point?
The loop invariant guarantees that throughout the search, every element before low is strictly less than the target and every element from high + 1 onward is strictly greater than the target. When low exceeds high, the two bounds cross and low points at the first element that is greater than or equal to the target. That is precisely where the target should go to preserve sorted order.
package com.bank.search;
public class InvariantTrace {
public static int searchInsertWithTrace(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
System.out.println("low=" + low + " high=" + high
+ " mid=" + mid + " val=" + arr[mid]);
if (arr[mid] == target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
System.out.println("Loop ended: low=" + low + " high=" + high);
return low;
}
public static void main(String[] args) {
int[] arr = {100, 300, 500, 700, 900};
int pos = searchInsertWithTrace(arr, 400);
System.out.println("Insert 400 at index: " + pos);
}
}
low=0 high=4 mid=2 val=500
low=0 high=1 mid=0 val=100
low=1 high=1 mid=1 val=300
Loop ended: low=2 high=1
Insert 400 at index: 2
How does it handle all edge cases?
The formula handles every edge case with no special code:
- Target smaller than everything:
lownever moves, returns 0 (insert at front). - Target larger than everything:
lowadvances past the end, returnsarr.length(append). - Target matches an element: returned early with that index.
- Empty array:
low = 0,high = -1, loop never runs, returns 0.
package com.bank.search;
public class AllEdgeCases {
public static int searchInsert(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return low;
}
public static void main(String[] args) {
int[] arr = {200, 400, 600, 800};
System.out.println("Smaller than all: " + searchInsert(arr, 100)); // 0
System.out.println("Larger than all: " + searchInsert(arr, 1000)); // 4
System.out.println("Exact match: " + searchInsert(arr, 600)); // 2
System.out.println("Between elements: " + searchInsert(arr, 500)); // 2
System.out.println("Empty array: " + searchInsert(new int[]{}, 5)); // 0
}
}
Smaller than all: 0
Larger than all: 4
Exact match: 2
Between elements: 2
Empty array: 0
How is this different from standard binary search?
| Feature | Standard Binary Search | Search Insert Position |
|---|---|---|
| On miss | Returns -1 | Returns insertion index (low) |
| Use case | Check existence | Find position for insertion |
| Return value | Index or -1 | Always a valid index |
| Loop body | Identical | Identical |
| After loop | return -1 | return low |
package com.bank.search;
import java.util.Arrays;
public class StandardVsInsert {
public static void main(String[] args) {
int[] arr = {100, 300, 500, 700};
int target = 400;
// Standard: returns -(insertion point) - 1
int stdResult = Arrays.binarySearch(arr, target);
int insertionPoint = -(stdResult) - 1;
System.out.println("Standard result: " + stdResult);
System.out.println("Insertion point: " + insertionPoint);
// Our version: returns insertion point directly
System.out.println("searchInsert: " + searchInsert(arr, target));
}
static int searchInsert(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
if (arr[m] == target) return m;
if (arr[m] < target) lo = m + 1;
else hi = m - 1;
}
return lo;
}
}
Standard result: -3
Insertion point: 2
searchInsert: 2
How is this used in a banking system?
At the National Bank of India, interest-rate tier thresholds are maintained in a sorted list. When a new threshold is defined or a customer's balance needs to be classified into a tier, this routine finds where it sits so the system either reads the matching tier or inserts the new threshold while preserving sorted order.
package com.bank.search;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
public class InterestRateTiers {
private final List<BigDecimal> thresholds = new ArrayList<>();
public void addThreshold(BigDecimal amount) {
int pos = searchInsert(amount);
if (pos < thresholds.size()
&& thresholds.get(pos).compareTo(amount) == 0) {
System.out.println(amount + " already exists at " + pos);
} else {
thresholds.add(pos, amount);
System.out.println("Inserted " + amount + " at " + pos);
}
}
private int searchInsert(BigDecimal target) {
int lo = 0, hi = thresholds.size() - 1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
int cmp = thresholds.get(m).compareTo(target);
if (cmp == 0) return m;
if (cmp < 0) lo = m + 1;
else hi = m - 1;
}
return lo;
}
public static void main(String[] args) {
InterestRateTiers tiers = new InterestRateTiers();
tiers.addThreshold(new BigDecimal("50000"));
tiers.addThreshold(new BigDecimal("100000"));
tiers.addThreshold(new BigDecimal("75000"));
tiers.addThreshold(new BigDecimal("50000"));
System.out.println("Tiers: " + tiers.thresholds);
}
}
Inserted 50000 at 0
Inserted 100000 at 1
Inserted 75000 at 1
50000 already exists at 0
Tiers: [50000, 75000, 100000]
What is the time and space complexity?
| Metric | Value |
|---|---|
| Time | O(log n) |
| Space | O(1) |
| Best case | O(1) when mid matches |
| Worst case | O(log n) |
How does this relate to Java's library methods?
Java's Arrays.binarySearch returns -(insertion point) - 1 when the target is not found. You can extract the insertion point with -(result) - 1. The searchInsert function is a cleaner version that returns the insertion point directly.
package com.bank.search;
import java.util.Arrays;
public class JavaLibrary {
public static void main(String[] args) {
int[] arr = {100, 300, 500, 700};
int found = Arrays.binarySearch(arr, 300);
System.out.println("Found 300: " + found);
int notFound = Arrays.binarySearch(arr, 400);
int insertAt = -(notFound) - 1;
System.out.println("Not found 400: raw=" + notFound + " insert at=" + insertAt);
}
}
Found 300: 1
Not found 400: raw=-3 insert at=2
What are common mistakes?
The most common mistake is returning high instead of low as the insertion point. When the loop ends, high is low - 1, and returning high gives a position one before the correct spot. Another mistake is memorizing "return low" without understanding the invariant, which makes it hard to adapt the template under interview pressure.
package com.bank.search;
public class ReturnHighBug {
// WRONG: returns high instead of low
public static int buggy(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
if (arr[m] == target) return m;
if (arr[m] < target) lo = m + 1;
else hi = m - 1;
}
return hi; // BUG: should be lo
}
// CORRECT
public static int correct(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
if (arr[m] == target) return m;
if (arr[m] < target) lo = m + 1;
else hi = m - 1;
}
return lo;
}
public static void main(String[] args) {
int[] arr = {100, 300, 500};
System.out.println("Buggy insert 200: " + buggy(arr, 200)); // 0 (wrong)
System.out.println("Correct insert 200: " + correct(arr, 200)); // 1
}
}
Buggy insert 200: 0
Correct insert 200: 1
Visual Overview
Sorted: [200, 400, 600, 800, 1000]
0 1 2 3 4
Target: 500 (not present)
Step 1: low=0 high=4 mid=2 val=600
600 > 500 -> high = 1
Step 2: low=0 high=1 mid=0 val=200
200 < 500 -> low = 1
Step 3: low=1 high=1 mid=1 val=400
400 < 500 -> low = 2
Loop ends: low=2 > high=1
Return low = 2 (insert between 400 and 600)
Result: [200, 400, 500, 600, 800, 1000]
^^^
Key Takeaway
Search insert position is standard binary search with one small but important change: instead of returning -1 when the target is absent, you return the final value of low, which is exactly the position where the target should be inserted to keep the array sorted.
The reason this works is the loop invariant. Throughout the search, every element before low is strictly less than the target and every element from high + 1 onward is strictly greater. When the pointers cross, low rests on the first element greater than or equal to the target, which is the correct insertion point. This handles all edge cases automatically: insert at front, at back, between elements, or match an existing element.
In a banking system at the National Bank of India, interest-rate tier thresholds are kept in a sorted list. When a new threshold is defined or a balance needs classification, this routine finds the correct slot in O(log n) time, either matching an existing tier or identifying where to insert a new one.
The senior-level insight is recognizing this as the lower-bound primitive. The same return-low pattern is the building block for counting elements below a value, inserting into sorted structures, and binary-search-on-answer templates. Understanding the invariant rather than memorizing the return value lets you adapt the template confidently.
Remember one sentence: when binary search ends without a match, the low pointer is exactly the insertion point because everything before it is smaller and everything after it is larger.
---