PROBLEM DESCRIPTION
Given a sorted array A and a target value B, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
SOLUTION
We can use standard binary search to solve this.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
public int searchInsert(ArrayList<Integer> a, int b) {
int l = 0;
int r = a.size() - 1;
while(l<=r){
int m = (l+r)/2;
// if value matches, return the current index m
if(a.get(m) == b){
return m;
// if current value is lesser than b
// we should look on the right side
}else if(a.get(m) < b){
l = m + 1;
// if current value is more than b
// we should look on the left side
}else{
r = m - 1;
}
}
return l;
}
}