35.|35. 搜索插入位置 35.搜索插入位置

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
【35.|35. 搜索插入位置】你可以假设数组中无重复元素。
示例 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
实现代码如下：

class Solution { public: int searchInsert(vector& nums, int target) { int i; int length = nums.size(); if (nums[length - 1] < target) { return length; } else if (target < nums[0]) { return 0; } for (i = 0; i < length; ++i) { if (nums[i] == target) { return i; } else if ((nums[i] < target) && (target < nums[i + 1])) { return (i+1); } }return -1; } };

运行结果：

文章图片

好的参考代码：

class Solution { public: int searchInsert(vector& nums, int target) { int n = nums.size(); if(n == 0) return 0; int left = 0; int mid = 0; while(left < n) { mid = (left + n) >> 1; if(nums[mid] < target) left = mid + 1; else if(nums[mid] == target) return mid; else n = mid; } return n; } }; ![在这里插入图片描述](https://img-blog.csdnimg.cn/20200601175323705.png)