LeetCode35.搜索插入位置

//個人學習筆記用

• 題目：
  給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。
  請必須使用時間複雜度為 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的位置

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