lintCode (60) Search Insert Position

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.

Have you met this question in a real interview? 

Yes

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

这个算是活学活用模板了。。。beg,end最后如果搜索不到，必然相邻， 那么就需要考虑3中情况，小于beg, 在二者之间，或大于end...当然了。。。还有corner case,空的时候。

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 31 32 33 34 35 36 37

class Solution { /** * param A : an integer sorted array * param target : an integer to be inserted * return : an integer */ public: int searchInsert(vector<int> &A, int target) { // write your code here if (A.empty()) return 0; int beg=0; int end=A.size()-1; while(beg+1<end){ int mid=beg+(end-beg)/2; if (A[mid]==target) end=mid; else if (A[mid]<target) beg=mid; else end=mid; } if (A[beg]==target){ return beg; } else if (A[end]==target){ return end; } if (target>A[beg] && target< A[end]){ return beg+1; } else if (target<A[beg]){ return beg; } else{ return end+1; } } };