嗨，大家好，我是袁廚（因為酷愛做飯，所以自己考取了廚師證）。之前一直看大家寫的部落格，學到了很多東西。然後最近萌生了自己寫的想法，將自己知道的分享給需要的同學。以後每天會為大家分享leetcode精選題目的各種題解和Python, JS, JQ, CSS, PHP, JAVA的一些小Demo。請大家關注我，一起交流學習吧。

         最近做了一個長久的計劃，就是把leetcode題目整理出來，由淺入深，由簡到繁都整理出來是一個宏大的工程，所以我打算每天整理一到兩個經典題目，完成這一個流程我相信肯定會收穫巨大的。如果想一起刷題的哥們，我們可以一起在群裡打卡，共同進步。大家可以搜尋tan45du_one或者掃描總結裡的二維條碼新增我為好友，我拉大家進群啊。

---

35.搜尋插入位置

• 題目描述
• 暴力解法
• • 做題思路：
  • 題目程式碼：
• 二分查詢法
• • 做題思路：
  • 題目程式碼：
• 總結

題目描述

暴力解法

做題思路：

這個題目雖然是簡單題目，但是通過率並不高，這是為什麼呢？應該是邊界情況思考不輕，做這個題目給我的第一想法就是利用二分查詢來做。這樣的效率會相對高一些。

插入情況無非就這幾種

（1）比陣列裡的任何值都小，插入頭部

（2）比陣列裡的任何值都大，插入尾部

（3）查詢到陣列元素，返回該處索引值

（4）陣列內無該元素，將其插入兩元素之間。

題目程式碼：

class Solution {
    public int searchInsert(int[] nums, int target) {
          //陣列為0的情況
          if(nums.length == 0){
              return 0;
          }
          //第一種情況
          if(target<=nums[0]){
              return 0;
          }
          //第二種情況
          if(target>nums[nums.length-1]){
              return nums.length;
          }
          for(int i = 1;i<nums.length;i++){
              //第三種情況
              if(nums[i]==target){
                  return i;
              }
              //第四種情況
              if(target>nums[i-1]&&target<nums[i]){
                  return i;
              }
          }
        return 0;
    }
}

二分查詢法

做題思路：

二分查詢主要針對有序陣列，根本原來相當於雙指標，一個指標指示最大值，一個指標指示最小值。下面我們通過一個例子進行說明我們想查詢的數位為48

上面的這個例子為一個有序陣列，紅色為low綠色為hig，藍色為mid。我們首先求出low和hig的中間位置的數和我們想要查詢的數進行比較，然後我們知道是高了還是低了。如果中間數大於被查詢的數，那麼我們就hig指標到mid的前一位。如果小於被查詢的數我們就以移動low指標到mid指標的後一位。該例子的中心思想就好比。平常我們讓朋友猜價格，當朋友猜錯的時候我們會給他提示，是猜高了還是低了，進而一步步的縮小範圍。直至猜中

題目程式碼：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            //中間值，與target對比
            int mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

---

總結

作者：LeetCode
連結：https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯絡作者獲得授權，非商業轉載請註明出處。