-
Notifications
You must be signed in to change notification settings - Fork 817
/
SearchInsertPosition.java
30 lines (28 loc) · 868 Bytes
/
SearchInsertPosition.java
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
package binary_search;
/**
* Created by gouthamvidyapradhan on 22/05/2017. 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.
*
* <p>You may assume no duplicates in the array.
*
* <p>Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0
*/
public class SearchInsertPosition {
public static void main(String[] args) throws Exception {
int[] A = {1, 3, 5, 6};
new SearchInsertPosition().searchInsert(A, 5);
}
public int searchInsert(int[] nums, int target) {
int pos = nums.length;
int s = 0, e = nums.length - 1;
while (s <= e) {
int m = s + (e - s) / 2;
if (nums[m] >= target) {
pos = m;
e = m - 1;
} else s = m + 1;
}
return pos;
}
}