力扣：35. 搜索插入位置

描述

給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。
請必須使用時間復雜度為 O(log n) 的算法。
示例 1:

輸入: nums = [1,3,5,6], target = 5
輸出: 2
示例 2:

輸入: nums = [1,3,5,6], target = 2
輸出: 1
示例 3:

輸入: nums = [1,3,5,6], target = 7
輸出: 4

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 為 無重復元素 的 升序 排列數組
-104 <= target <= 104

1.暴力解法

從數組的左邊遍歷到右邊，如果遇到相等的元素，直接返回下標；如果遇到第 1 個嚴格大于 target 的元素，返回這個元素的下標；如果數組里所有的元素都嚴格小于 target，返回數組的長度 len。
代碼如下：

#include<iostream>
#include<vector>
using namespace std;
class Solution{
public:int searchInsert(vector<int>& nums, int target){int num = 0;int tmp = 0;for(int i = 0; i < nums.size(); i++){if(nums[i] == target){return i;}if(nums[i] > target && num == 0){tmp = i;num = 1;}}if(num == 0){return nums.size();}else {return tmp;}}
};int main(){Solution solution;vector<int> nums = {1,3,5,6,9,13,27,34,49,58,60};int target = 44;int insertPostion = solution.searchInsert(nums,target);cout << "The inset postion for target " << target << " is " << insertPostion << endl;return 0;
}

![在這里插入圖片描述](https://img-blog.csdnimg.cn/direct/a2d9f9092b774b24b3842c2484f87f19.png

2.二分查找

在有序數組中查找插入元素的位置，顯然可以使用二分查找。提供的思路是「排除法」，思路是：在循環的過程中，不斷排除不需要的解，最后剩下的那個元素的位置就一定是插入元素的位置。

具體來說：

首先，插入位置有可能在數組的末尾，需要單獨判斷，此時返回數組的長度；
否則，根據示例和暴力解法的分析，插入的位置是大于等于 target 的第 1 個元素的位置。
因此，嚴格小于 target 的元素一定不是解，在循環體中將左右邊界 left 和 right 逐漸向中間靠攏，最后 left 和 right 相遇，則找到了插入元素的位置。根據這個思路，可以寫出如下代碼。

#include<iostream>
#include<vector>
using namespace std;
class Solution{
public:int insearchInsert(vector<int> & nums, int target){int len = nums.size();if(len == 0){return 0;}if(nums[len - 1] < target){return len;}int left = 0;int right = len - 1;while(left < right){int mid = left + ((right - left) / 2);if(nums[mid] < target){left = mid + 1;}else {right = mid;}}return left;}
};
int main()
{Solution solution;vector<int> nums = {1,3,5,6,9,13,27,34,49,58,60};int target = 44;int insertPostion = solution.insearchInsert(nums,target);cout << " The target " << target << " is " << insertPostion << endl;return 0;
}

時間復雜度：O(log?n)O(\log n)O(logn)，其中 nnn 為數組的長度。二分查找所需的時間復雜度為 O(log?n)O(\log n)O(logn)。

空間復雜度：O(1)O(1)O(1)。我們只需要常數空間存放若干變量。

力扣：35. 搜索插入位置