LeetCode刷题（30）～搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

  

 

  
1
  
2
 

示例 2:

输入: [1,3,5,6], 2
输出: 1

  

 

  
1
  
2
 

示例 3:

输入: [1,3,5,6], 7
输出: 4

  

 

  
1
  
2
 

示例 4:

输入: [1,3,5,6], 0
输出: 0

  

 

  
1
  
2
 

解答 By 海轰

提交代码（暴力解法）

  int searchInsert(vector<int>& nums, int target) { int len=nums.size(); for(int i=0;i<len;++i) if(nums[i]==target) return i; if(nums[0]>target) return 0; if(nums[len-1]<target) return len; for(int i=1;i<len;++i) if(nums[i-1]<target&&nums[i]>target) return i; return 0; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

运行结果

解答

二分查找

int searchInsert(vector<int>& nums, int target) { int left=0; int right=nums.size()-1; while(left<=right) { int mid=(left+right)/2; if(nums[mid]<target) left=mid+1; else right=mid-1; } return left; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

暴力解法（优化）

 int searchInsert(vector<int>& nums, int target) { int len=nums.size(); for(int i=0;i<len;++i) if(nums[i]>=target) return i; return len; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/107884975