Search Any/First/Last/Insert Position
Search Any Position (LC.457)
Find any position of a target number in a sorted array. Return -1 if target does not exist.
Example
Input: [1, 2, 2, 4, 5, 5], target = 2
Return: either 1 or 2
Input: [1, 2, 2, 4, 5, 5], target = 6
Return: -1
Analysis
This is the vanilla binary search. We can use a no-brainer template. Here we will go over details and understand how this template was made. Oh and the brute force approach is just to scan the array and find the target.
While Loop
For any array question, we first check for the null/empty input. We want to set the base case as start and end next to each other. The merit of this approach is not very clear at this stage. But later we will see why this is very helpful. If the median < target, search the right section. If the median > target, search the left section. Solve the base case in the end.
public classicBS(int A[], target) {
if (A == null || A.length == 0)
return -1;
int start = 0, mid, end = A.length - 1;
// stop when start and end next to each other
while (start + 1 < end) {
// mid = (start + end) / 2; might overflow
mid = start + (end - start) / 2;
if (A[mid] == target) {
return mid;
} else if (A[mid] < target) {
// median is less than target, search in the right section
start = mid + 1;
} else {
// median is bigger than target, search in the left section
end = mid - 1;
}
}
// start is next to end now
if (A[start] == target) {
return start;
} else if (A[end] == target) {
return end;
} else {
return -1;
}
}
Recursion
This might feel more natural to write but again recursion needs space on call stack to work. When the number is large enough, we might encounter stack overflow.
public int findPosition(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}
return bsHelper(A, target, 0, A.length -1);
}
private int bsHelper(int[] A, int target, int start, int end) {
// base case
if (start + 1 >= end) {
if (A[start] == target) {
return start;
} else if (A[end] == target) {
return end;
} else {
return -1;
}
}
// decrease
int mid = start + (end - start) / 2;
// conquer
if (A[mid] == target) {
return mid;
} else if (A[mid] < target) {
// the median < target, search right section
// +/-1 since mid is not the target
return bsHelper(A, target, mid + 1, end);
} else {
// the median > target, search left section
return bsHelper(A, target, start, mid - 1);
}
}
Search First Position (LC.14)
Given a sorted array and a target, find the first occurrence of this target.
Example
Input: [1, 2, 2, 4, 5, 5], target = 2
Return: 1 (not 2)
Analysis
Now we see why we need to make our base case where start and end next to each other. For this question, we only have to change when A[mid] == target, end = mid.
Code
// first position of target
// don't return mid when == target, set end = mid
public firstPosition(int A[], target) {
if (A == null || A.length == 0)
return -1;
int start = 0, mid, end = A.length - 1;
// stop when start and end next to each other
while (start + 1 < end) {
// mid = (start + end) / 2; might overflow
mid = start + (end - start) / 2;
if (A[mid] == target) {
end = mid;
} else if (A[mid] < target) {
// median is less than target, search in the right section
start = mid + 1;
} else {
// median is bigger than target, search in the left section
end = mid - 1;
}
}
// start is next to end now
if (A[start] == target) {
return start;
} else if (A[end] == target) {
return end;
} else {
return -1;
}
}
Search Last Position (LC.458)
Given a sorted array and a target, find the last occurrence of this target.
Example
Input: [1, 2, 2, 4, 5, 5], target = 2
Return: 2 (not 1)
Analysis
When A[mid] == target, start = mid. For the base case, check A[end] == target first.
Code
// last pos of target
// set start = mid, return end first after while loop
public firstPosition(int A[], target) {
if (A == null || A.length == 0)
return -1;
int start = 0, mid, end = A.length - 1;
// stop when start and end next to each other
while (start + 1 < end) {
// mid = (start + end) / 2; might overflow
mid = start + (end - start) / 2; // notice write <= might get bug easily
if (A[mid] == target) {
start = mid;
} else if (A[mid] < target) {
// median is less than target, search in the right section
start = mid + 1;
} else {
// median is bigger than target, search in the left section
end = mid - 1;
}
}
// start is next to end now
if (A[end] == target) {
return end;
} else if (A[start] == target) {
return start;
} else {
return -1;
}
}
Search Insert Position (LC.35)
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
Assume no duplicates in the input array.
Example
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
Analysis
Vanilla binary search with a tweak. If target is found, then just return the index. 3 cases for target not found:
- target < A[start], return start
- A[start] < target < A[end], return end
- A[end] < target < A[end+1], return end + 1
Code
public int searchInsert(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int start = 0, mid, end = nums.length - 1;
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
// the median < target, search the right section
start = mid + 1;
} else {
// the median > target, search the left section
end = mid - 1;
}
}
// base case start and end next to each other
if (target <= nums[start]) {
return start;
} else if (target <= nums[end]) {
return end;
} else {
// nums[end] < target < nums[end+1]
return end + 1;
}
}
Conclusion
The most transparent binary search question follows this format: We can check(A[index]) = {T, F}, then the array becomes [T, T, T, T, T, F, F, F, F, F]. We want to find the last T or the first F or in between.