Definition
- First position search – a binary search that, on finding the target, records the index and continues searching leftward by setting
high = mid - 1. - Last position search – a binary search that, on finding the target, records the index and continues searching rightward by setting
low = mid + 1. - No early return – unlike standard binary search, neither search returns immediately on a match; both push toward the boundary.
- O(log n) total – each search is O(log n), so finding both boundaries is still O(log n).
- Count bonus – the number of matching elements is
last - first + 1with no extra pass.
The National Bank of India's transaction ledger is sorted by amount, and many transactions share the exact same round amount like fifty thousand rupees. To find the range of rows for a given amount, the clerk does one binary search that, whenever it lands on the amount, keeps nudging further left to find the very first such row, and a second binary search that keeps nudging right to find the very last such row.
Understanding the Concepts
What is the problem?
Given a sorted array that may contain duplicates and a target value, find the first (leftmost) and last (rightmost) index where the target appears. If the target is not present, return [-1, -1]. The solution must run in O(log n) time.
A plain binary search finds some occurrence of the target, but with duplicates it could land anywhere in the run. We need the exact boundaries.
package com.bank.search;
public class FirstLastPosition {
public static int[] searchRange(int[] amounts, int target) {
int first = findFirst(amounts, target);
if (first == -1) return new int[]{-1, -1};
int last = findLast(amounts, target);
return new int[]{first, last};
}
private static int findFirst(int[] arr, int target) {
int low = 0, high = arr.length - 1, result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
high = mid - 1; // keep searching left
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
private static int findLast(int[] arr, int target) {
int low = 0, high = arr.length - 1, result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
result = mid;
low = mid + 1; // keep searching right
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] txnAmounts = {100, 200, 200, 200, 300, 400, 500};
int[] range = searchRange(txnAmounts, 200);
System.out.println("First: " + range[0] + ", Last: " + range[1]);
System.out.println("Count: " + (range[1] - range[0] + 1));
}
}
First: 1, Last: 3
Count: 3
Why does the bias work?
By never returning early on a match and always pushing toward the desired edge, the last stored match is guaranteed to be the extreme occurrence. For the first-position search, every time we find the target we move high below mid, so any earlier occurrence would be found on a later iteration. The loop only ends when no more leftward movement is possible, so the last recorded index is the leftmost.
package com.bank.search;
public class BiasExplained {
public static int findFirstWithTrace(int[] arr, int target) {
int low = 0, high = arr.length - 1, result = -1;
int step = 0;
while (low <= high) {
step++;
int mid = low + (high - low) / 2;
System.out.println("Step " + step + ": low=" + low
+ " high=" + high + " mid=" + mid + " val=" + arr[mid]);
if (arr[mid] == target) {
result = mid;
System.out.println(" Match! Record " + mid + ", search left");
high = mid - 1;
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {100, 200, 200, 200, 200, 300};
int first = findFirstWithTrace(arr, 200);
System.out.println("First position: " + first);
}
}
Step 1: low=0 high=5 mid=2 val=200
Match! Record 2, search left
Step 2: low=0 high=1 mid=0 val=100
Step 3: low=1 high=1 mid=1 val=200
Match! Record 1, search left
First position: 1
How is this different from standard binary search?
Standard binary search returns immediately on finding the target. The boundary search does not return early. It records the match and continues toward the desired edge. This single difference is what makes it find the first or last occurrence.
| Behavior | Standard Search | First Position | Last Position |
|---|---|---|---|
| On match | Return immediately | Record, search left | Record, search right |
| Returns | Any occurrence | Leftmost occurrence | Rightmost occurrence |
| Time | O(log n) | O(log n) | O(log n) |
package com.bank.search;
import java.util.Arrays;
public class StandardVsBoundary {
public static void main(String[] args) {
int[] arr = {100, 200, 200, 200, 300};
// Standard: finds index 2 (some occurrence)
System.out.println("Standard: " + Arrays.binarySearch(arr, 200));
// Boundary: finds index 1 (first) and 3 (last)
System.out.println("First: " + findFirst(arr, 200));
System.out.println("Last: " + findLast(arr, 200));
}
static int findFirst(int[] arr, int t) {
int lo = 0, hi = arr.length - 1, res = -1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
if (arr[m] == t) { res = m; hi = m - 1; }
else if (arr[m] < t) lo = m + 1;
else hi = m - 1;
}
return res;
}
static int findLast(int[] arr, int t) {
int lo = 0, hi = arr.length - 1, res = -1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
if (arr[m] == t) { res = m; lo = m + 1; }
else if (arr[m] < t) lo = m + 1;
else hi = m - 1;
}
return res;
}
}
Standard: 2
First: 1
Last: 3
How do you count occurrences efficiently?
Once you have the first and last indices, the count is last - first + 1. This avoids a separate linear scan through the duplicates.
package com.bank.search;
public class CountOccurrences {
public static void main(String[] args) {
int[] amounts = {100, 200, 200, 200, 200, 200, 300, 400};
int first = 1; // from findFirst
int last = 5; // from findLast
int count = last - first + 1;
System.out.println("Amount 200 appears " + count + " times");
}
}
Amount 200 appears 5 times
What are the edge cases?
The important edge cases are: target not present (return [-1, -1]), all elements are the target (first = 0, last = n-1), target at position 0 only, and target at position n-1 only.
package com.bank.search;
import java.util.Arrays;
public class EdgeCases {
public static void main(String[] args) {
System.out.println("Not present: " + Arrays.toString(searchRange(new int[]{1,2,3}, 5)));
System.out.println("All same: " + Arrays.toString(searchRange(new int[]{2,2,2}, 2)));
System.out.println("First only: " + Arrays.toString(searchRange(new int[]{2,3,4}, 2)));
System.out.println("Last only: " + Arrays.toString(searchRange(new int[]{1,2,3}, 3)));
System.out.println("Single match: " + Arrays.toString(searchRange(new int[]{5}, 5)));
System.out.println("Empty: " + Arrays.toString(searchRange(new int[]{}, 5)));
}
static int[] searchRange(int[] a, int t) {
int f = find(a, t, true);
if (f == -1) return new int[]{-1, -1};
return new int[]{f, find(a, t, false)};
}
static int find(int[] a, int t, boolean leftBias) {
int lo = 0, hi = a.length - 1, res = -1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
if (a[m] == t) {
res = m;
if (leftBias) hi = m - 1; else lo = m + 1;
} else if (a[m] < t) lo = m + 1;
else hi = m - 1;
}
return res;
}
}
Not present: [-1, -1]
All same: [0, 2]
First only: [0, 0]
Last only: [2, 2]
Single match: [0, 0]
Empty: [-1, -1]
What is the time and space complexity?
| Metric | Value |
|---|---|
| Time | O(log n) for each search, O(log n) total |
| Space | O(1) |
| Best case | O(1) if midpoint is the only occurrence |
| Worst case | O(log n) even with all duplicates |
How is this used in a banking system?
At the National Bank of India, a day's transactions are stored sorted by amount. Many transactions share the same round amount like a popular fifty-thousand-rupee transfer. The audit team needs the first and last index of a given amount to slice out that contiguous block for review. These two searches give exact boundaries in logarithmic time.
package com.bank.search;
import java.math.BigDecimal;
public class BankingAuditSlice {
public static int findFirst(BigDecimal[] txns, BigDecimal target) {
int lo = 0, hi = txns.length - 1, res = -1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
int cmp = txns[m].compareTo(target);
if (cmp == 0) { res = m; hi = m - 1; }
else if (cmp < 0) lo = m + 1;
else hi = m - 1;
}
return res;
}
public static int findLast(BigDecimal[] txns, BigDecimal target) {
int lo = 0, hi = txns.length - 1, res = -1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
int cmp = txns[m].compareTo(target);
if (cmp == 0) { res = m; lo = m + 1; }
else if (cmp < 0) lo = m + 1;
else hi = m - 1;
}
return res;
}
public static void main(String[] args) {
BigDecimal[] txns = {
new BigDecimal("10000"), new BigDecimal("50000"),
new BigDecimal("50000"), new BigDecimal("50000"),
new BigDecimal("75000"), new BigDecimal("100000")
};
BigDecimal target = new BigDecimal("50000");
int first = findFirst(txns, target);
int last = findLast(txns, target);
System.out.println("Audit slice: index " + first + " to " + last);
System.out.println("Matching transactions: " + (last - first + 1));
}
}
Audit slice: index 1 to 3
Matching transactions: 3
What are common interview follow-up questions?
- Interviewers often extend this problem:
- Count the number of occurrences (answer: last - first + 1).
- Find the first element greater than the target (upper bound).
- Find the insertion position if the target were to be inserted.
- Apply the same pattern in a rotated sorted array.
Visual Overview
Sorted: [100, 200, 200, 200, 200, 300, 400]
0 1 2 3 4 5 6
Find First (target = 200):
Step 1: mid=3 val=200 -> match, record 3, go LEFT
Step 2: mid=1 val=200 -> match, record 1, go LEFT
Step 3: mid=0 val=100 -> less, go RIGHT
Result: first = 1
Find Last (target = 200):
Step 1: mid=3 val=200 -> match, record 3, go RIGHT
Step 2: mid=5 val=300 -> greater, go LEFT
Step 3: mid=4 val=200 -> match, record 4, go RIGHT
Result: last = 4
Range: [1, 4] Count: 4
Key Takeaway
Finding the first and last position of a target in a sorted array with duplicates is solved with two modified binary searches. The key insight is that when you land on a match, you do not stop. For the first position, you record the match and continue searching leftward by moving high below mid. For the last position, you record the match and continue rightward by moving low above mid. Each search is O(log n), so the whole operation stays logarithmic.
This is the canonical lower-bound and upper-bound pattern. The reason it works is that by always pushing toward the edge you care about and never returning early, any occurrence further in that direction would be discovered on a later iteration, so the final recorded index is guaranteed to be the extreme one.
In a banking system at the National Bank of India, a day's transactions sorted by amount often contain many entries with the same popular amount. The audit team needs the first and last index to slice out the contiguous block for review, and these two searches give exact boundaries without scanning the entire array.
A practical bonus is that once you have the first and last index, the count of matching entries is simply last - first + 1, so you report the count instantly with no extra pass.
Remember one sentence: to find the first and last position, run two binary searches that record the match and keep pushing toward the boundary instead of returning early.
---