LeetCode35.搜索插入位置-526互联

//个人学习笔记用

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

参考题解--代码随想录

暴力解法：

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

//解析：他是要返回位置，所以可以不用插入数据，直接返回位置即可

二分解法

class Solution {
public:
	int searchInsert(vector<int>& nums, int target) {
    if(nums.empty())
    return 0;
    int left = 0;
    int right = nums.size() - 1;
    while(left <= right){
        //int middle = (left + right)/2;
        int middle = left + ((right - left)/2);  
//左右变量一直在变化，那么要计算middle就要在循环里面定义，即随着left 、right的变化，middle也在变化
        	if(nums[middle] < target)
        	left = middle + 1;
        	else if(nums[middle] > target)
    	    right = middle -1;
	        else
            return middle;
  	  }
      return right + 1;
	}
};

//解析：他是要返回位置，所以可以不用插入数据，直接返回位置即可