//个人学习笔记用

• 题目：
  给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
  请必须使用时间复杂度为 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;
  	}
  };
  
  //解析：他是要返回位置，所以可以不用插入数据，直接返回位置即可
  
  
  
  

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;           
    }
};



//二分查找，left、right从两侧向目标值靠拢，直到left = right，再执行一次操作，
//无论执行哪一个，那么，right 一定会小于 left，那最后的目标值，应插入到right（最小值）+1的位置

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