35. 搜索插入位置
时间：7月17日
知识点：二分查找
题目链接：https://leetcode-/problems/search-insert-position/
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例1
输入：
[1,3,5,6] , 5
输出：
2
示例2
输入：
[1,3,5,6] , 2
输出：
1
示例3
输入：
[1,3,5,6] , 7
输出：
4
示例4
输入：
[1,3,5,6] , 0
输出：
0
解法
参考网址
是二分查找问题，但是又有所不同二分查找有两种模版在循环体内查找目标元素，把区间分成三份
[mid] return
[left,mid-1] end = mid-1
[mid+1,right] left = mid+1
int searchInsert(vector<int>& nums, int target) {int len = nums.size();int left = 0;int right = len - 1;while (left <= right) {int mid = left + (right - left) / 2;//int mid = (left + right) / 2; right和left很大时可能会溢出if (nums[mid] == target) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}
在循环体内排除一定不存在目标答案的区间，把区间分成两份，考虑中间元素[mid]在什么情况下一定不是目标元素[left,mid] right = mid
[mid+1,right] left = mid+1
//(本题就是这个情况，target < nums[mid] 时一定不是解)int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size()-1;while(left<right){int mid = left+(right-left)/2;if (nums[mid]==target)return mid;else if(check(mid))left = mid+1;elseright = mid;}return left;}
[left,mid-1] right = mid-1
[mid,right] left = mid
有可能陷入死循环 只有看到 left = mid 的时候，才需要调整成为上取整，
nums[0]=0 nums[1]=5
left = 0 right = 1 mid = first+(end-first)/2 = 0 求
left = mid right不变 陷入死循环
解决方法 mid = first+(end-first+1)/2 = 1
int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size()-1;while(left<right){int mid = left+(right-left+1)/2;if (nums[mid]==target)return mid;else if(check(mid))left = mid;elseright = mid-1;}return left;}
这里要求的是大于等于 target 的第 1 个元素的位置。
代码
#include <stdio.h>#include <vector>#include <iostream>using namespace std;class Solution {public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int left = 0;int right = n - 1; // 定义target在左闭右闭的区间里，[left, right] while (left <= right) {// 当left==right，区间[left, right]依然有效int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // target 在左区间，所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，所以[middle + 1, right]} else {// nums[middle] == targetreturn middle;}}// 分别处理如下四种情况// 目标值在数组所有元素之前 [0, -1]// 目标值等于数组中某一个元素 return middle;// 目标值插入数组中的位置 [left, right]，return right + 1// 目标值在数组所有元素之后的情况 [left, right]， return right + 1return right + 1;}};/*class Solution {public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int left = 0;int right = n; // 定义target在左闭右开的区间里，[left, right) targetwhile (left < right) { // 因为left == right的时候，在[left, right)是无效的空间int middle = left + ((right - left) >> 1);if (nums[middle] > target) {right = middle; // target 在左区间，在[left, middle)中} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，在 [middle+1, right)中} else { // nums[middle] == targetreturn middle; // 数组中找到目标值的情况，直接返回下标}}// 分别处理如下四种情况// 目标值在数组所有元素之前 [0,0)// 目标值等于数组中某一个元素 return middle// 目标值插入数组中的位置 [left, right) ，return right 即可// 目标值在数组所有元素之后的情况 [left, right)，return right 即可return right;}};*/int main(){vector<int> v(4,0);v[0]=1;v[1]=3;v[2]=5;v[3]=6;vector<int> w(3,0);w[0]=1;w[1]=3;w[2]=5;vector<int> z(1,0);z[0]=1;Solution s;cout<<s.searchInsert(v,2);}
今天也是爱zz的一天哦！
如果觉得《Leetcode刷题笔记 35.搜索插入位置（详细说明二分查找）》对你有帮助，请点赞、收藏，并留下你的观点哦！
