题目描述
原题链接 :
35. 搜索插入位置 - 力扣（LeetCode） (leetcode-cn.com)
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
|
1
2
|
输入: nums = [1,3,5,6], target = 5输出: 2 |
示例 2:
|
1
2
|
输入: nums = [1,3,5,6], target = 2输出: 1 |
示例 3:
|
1
2
|
输入: nums = [1,3,5,6], target = 7输出: 4 |
提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为 无重复元素 的 升序 排列数组
-10^4 <= target <= 10^4
思路分析
首先明确题目的含义：
（1）数组是有序的；
（2）如果含有与目标值相等，则返回目标值下标，若不同，则按顺序排序获取下标
思路：采用二分搜索法的策略，获取中间数据的大小，缩短数组的大小定位区间，如在数组中间的前一段，数组中间的后一段
获取下标i的值arrs[i]>=target,进行相应的下标返回
AC 代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution { public int searchInsert(int[] nums, int target) { int index = (nums.length / 2); if (nums[index] >= target) { return compareByIndex(nums, 0, index+1, target); } else return compareByIndex(nums, index+1, nums.length, target); } private int compareByIndex(int[] nums, int start, int end, int target) { for (int i = start; i < end; i++) { if (nums[i] >= target) { return i; } } return end; }} |
总结
这种查找位置的，肯定二分法是合适的，即使不能直接套用二分法的公式，也是二分法的思想，变种。
参考
思维导图整理: 总结了二分查找的通用模板写法, 彻底解决几个易混淆问题 - 搜索插入位置
优先考虑边界情况 红蓝标记解法
首先考虑target是否>=nums[numsSize-1],大于则返回numsSize，等于则返回numsSize-1;
再检查底线，若小于等于nums[0]则返回nums[0]；
else
定义左边界left=0，右边界right=numsSize-1；
进入循环，缩小边界，直到left+1=right；
若找到则直接返回，循环结束时未找到则返回left+1（在left与right之间）
代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
int searchInsert(int* nums, int numsSize, int target){ if(nums[0]>=target) { return 0; } else if(nums[numsSize-1]<target) { return numsSize; } else if(nums[numsSize-1]==target) { return numsSize-1; } else{ int r=numsSize-1; int i=0; while(i+1!=r) { int mid=(i+r)/2; if(nums[mid]>target ){ r=mid;} else if(nums[mid]<target) i=mid; else{ return mid; } } return i+1; }} |
以上就是Go语言题解LeetCode35搜索插入位置示例详解的详细内容，更多关于Go语言搜索插入位置的资料请关注服务器之家其它相关文章！
原文链接：https://juejin.cn/post/7173274268069953572
