E
一般的binary search.
在结尾判断该return 哪个position。
```
/*
28% Accepted
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.
You may assume no duplicates in the 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
Tags Expand
Binary Search Array Sorted Array
*/
/*
Recap 12.08.2015
Find the occurance of the target, return it.
If not found, at the point, start + 1 = end
return the insert position at start + 1
*/
public class Solution {
public int searchInsert(int[] A, int target) {
if (A == null || A.length == 0) {//Insert at 0 position
return 0;
}
int start = 0;
int end = A.length - 1;
int mid = start + (end - start)/2;
while (start + 1 < end) {
mid = start + (end - start)/2;
if (A[mid] == target) {
return mid;
} else if (A[mid] > target) {
end = mid;
} else {
start = mid;
}
}
if (A[start] >= target) {
return start;
} else if (A[start] < target && target <= A[end]) {
return end;
} else {
return end + 1;
}
}
}
//older version
public class Solution {
/**
* param A : an integer sorted array
* param target : an integer to be inserted
* return : an integer
*/
public int searchInsert(ArrayList A, int target) {
// write your code here
int start = 0;
int end = A.size() - 1;
int mid;
if (A == null || A.size() == 0 || target <= A.get(0)) {
return 0;
}
//find the last number less than target
while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A.get(mid) == target) {//Since no duplicates, return when found
return mid;
} else if (A.get(mid) < target) {
start = mid;
} else {
end = mid;
}
}
//Always 2 elements left to check, first:start, second: end
if (A.get(end) == target) {
return end;
}
if (A.get(end) < target) {
return end + 1;
}
if (A.get(start) == target) {
return start;
}
return start + 1;
}
}
```