文章目录

• 一【题目类别】
• 二【题目难度】
• 三【题目编号】
• 四【题目描述】
• 五【题目示例】
• 六【题目提示】
• 七【解题思路】
• 八【时间频度】
• 九【代码实现】
• 十【提交结果】

一【题目类别】

• 数组

二【题目难度】

• 简单

三【题目编号】

• 35.搜索插入位置

四【题目描述】

• 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
• 请必须使用时间复杂度为 $O(logn)$ 的算法。

五【题目示例】

• 示例 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 < = n u m s . l e n g t h < = 104 1 <= nums.length <= 10^4 1<=nums.length<=104
• − 104 < = n u m s [ i ] < = 104 -10^4 <= nums[i] <= 10^4 −104<=nums[i]<=104
• $nums为无重复元素的升序排列数组$
• − 104 < = t a r g e t < = 104 -10^4 <= target <= 10^4 −104<=target<=104

七【解题思路】

• 看到题目要求的时间复杂度还有有序数组，首选二分查找，对于二分查找应该是很简单的算法。但是有一点需要强调，如果没有找到对应的值，则右指针会指向最大小于target的值，左指针指向最小大于target的值，明白这个就知道为什么最后返回左指针了

八【时间频度】

• 时间复杂度：$O(logn)$，其中$n$为数组长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

package Array;public class p35_SearchCaretPosition {    public static void main(String[] args) { int[] nums = {1, 3, 5, 6}; int target = 5; int res = searchInsert(nums, target); System.out.println(res);    }    public static int searchInsert(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) {     int mid = left + (right - left) / 2;     if (nums[mid] == target) {  return mid;     } else if (nums[mid] < target) {  left = mid + 1;     } else if (nums[mid] > target) {  right = mid - 1;     } } return left;    }}

2. C语言版

#includeint searchInsert(int* nums, int numsSize, int target){int left = 0, right = numsSize - 1;while (left <= right){int mid = (left + right) / 2;if (nums[mid] == target){return mid;}else if (nums[mid] < target){left = mid + 1;}else if (nums[mid] > target){right = mid - 1;}}return left;}/*主函数省略*/

十【提交结果】

1. Java语言版
   

2. C语言版