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

思路1：直觀的想法，遍歷數(shù)組，一旦當(dāng)前元素>=target，當(dāng)前元素的位置即為插入位置，邊界問題處理一下即可。時(shí)間復(fù)雜度：O(n)

class Solution { public:int searchInsert(int A[], int n, int target) {if(target > A[n-1])return n;else { for(int i = 0; i < n; i++) {if(A[i] >= target)return i;}}} };
思路2：由于給定數(shù)組為已經(jīng)排好序的，可以使用二分查找，比較A[mid]與target的大小。時(shí)間復(fù)雜度：O(logn)

class Solution { public:int searchInsert(int A[], int n, int target) {int start = 0;int end = n - 1;int mid = 0;while(end >= start) {mid = (start + end) / 2;if(target == A[mid])return mid;else if(target > A[mid])start = mid + 1;elseend = mid - 1;}if(target > A[mid])return mid + 1;elsereturn mid;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode --Search Insert Position的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。