[LintCode/LeetCode] Search Insert Position
文章目录
Problem
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
Challenge
O(log(n)) time
Note
标准二分法题目。
Solution
public class Solution {
public int searchInsert(int[] A, int target) {
int start = 0, end = A.length-1, mid;
if (A == null || A.length == 0) return 0;
while (start <= end) {
mid = (start+end)/2;
if (A[mid] == target) return mid;
else if (A[mid] < target) start = mid+1;
else end = mid-1;
}
return start;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论