Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
32 lines (29 sloc) 735 Bytes
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.
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
-------------------------------------------
solution:
//二分查找,如果找到直接返回下标,没有找到循环停止时l所指即为插入的位置
int searchInsert(int A[], int n, int target)
{
if(n == 0)
return 0;
int l = 0;
int r = n - 1;
while(l <= r)
{
int mid = (l + r) / 2;
if(A[mid] == target)
return mid;
else if(A[mid] < target)
l = mid + 1;
else
r = mid - 1;
}
return l;
}