[LintCode/LeetCode] Search Insert Position

2016-8-16 12:47| 发布者: zhangjf| 查看: 682| 评论: 0

摘要: 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 a ...

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;
}
}

复制代码

收藏邀请

上一篇：[LintCode/LeetCode] N-Queens I & II [N皇后]下一篇：[LintCode/LeetCode] Search in Rotated Sorted Array I & II

		自动登录	找回密码
密码			立即注册

[LintCode/LeetCode] Search Insert Position

最新评论

相关分类