Leetcode35. 搜索插入位置

问题

水题

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

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

代码

自己写麻烦了，时间复杂度不如标答快！

 1 class Solution {
 2 public:
 3     int searchInsert(vector<int>& nums, int target) {
 4         if(target < nums[0] || nums.size() == 0) return 0;
 5         if(target > nums[nums.size()-1] ) return nums.size();
 6         
 7         for(int i = 0;i < nums.size();i++) {
 8             if(nums[i] == target ) 
 9                 return i;
10             if(nums[i] < target && nums[i+1] > target) 
11                 return i+1;
12         }
13          return 0;
14     }
15 };

于是又重新写了折半搜索。。。。

 1 class Solution {
 2 public:
 3     int searchInsert(vector<int>& nums, int target) {
 4        int low = 0,high = nums.size()-1;
 5        while(low <= high){
 6            int mid = (low + high) /2;
 7            if(nums[mid] == target ) return mid;
 8            else if(nums[mid] < target) low = mid + 1;
 9            else high = mid - 1;
10        }
11        return low;
12     }
13 };

总结：

1.本题出现了未结束的返回值错误

Line 14: Char 5: fatal error: control may reach end of non-void function [-Wreturn-type] }

应该仔细检查每一个控制流是否都有返回值

程序最后加上 return 0；问题解决！！

2. 关于折半搜索的跳出循环条件一定是low <= high 而不是小于，如果小于将会漏掉边界条件。

这也是自己之前没有注意的一个点！！ https://blog.csdn.net/yuanren201/article/details/105336591