搜索旋轉排序陣列（middle）

更好的閱讀體驗應該是：

審題-思考
答題
整理-歸納

一、題目

LeetCode：33.搜索旋轉排序陣列

給你一個整數陣列 nums ，和一個整數 target ，

該整數陣列原本是按升序排列，但輸入時在預先未知的某個點上進行了旋轉，（例如，陣列 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] ），

請你在陣列中搜索 target ，如果陣列中存在這個目標值，則回傳它的索引，否則回傳 -1 ，

示例 1：

輸入：nums = [4,5,6,7,0,1,2], target = 0
輸出：4

二、二分法解題

二分查找是一種基于比較目標值和陣列中間元素的教科書式演算法，

如果目標值等于中間元素，則找到目標值，
如果目標值較小，繼續在左側搜索，
如果目標值較大，則繼續在右側搜索，

分析模版

確定
- left = 0;
- right = nums.length - 1;
- mid = left + ((right - left) >> 1);
終止搜索條件為 left <= right，
判斷中間值是在有序區間內還是在無序區間內(因為只有1個轉折點)
- nums[mid] > nums[left]，則 mid 在左側升序區間
- nums[mid] < nums[left]，則 mid 在右側升序區間
繼續判斷 target 與有序區間的邊界進行比較
- 確定 mid 在左側升序區間，target 與左區間（[left, mid]）的最大值比較，即 target <= nums[mid] && target >= nums[left] 時，target 在左側區間，可以直接舍棄右側部分，反之則舍棄左側部分
- 確定 mid 在右側升序區間，target 與右區間（[mid, right]）的最小值比較，即 target >= nums[mid] && target <=> nums[right] 時，target 在右側區間，可以直接舍棄左側部分，反之則舍棄右側部分

Javasciprt 代碼

var guessNumber = function(n) {
  let left = 0; // 初始左邊界
  let right = n; // 初始右邊界
  while (left <= right) {
    var mid = left + Math.floor((right - left) / 2); //防止溢位
    if (guess(mid) === 0) {
      return mid;
    } else if (guess(mid) === 1) {
      // 目標值大于中值，則中間左側可以拋棄了
      left = mid + 1;
    } else {
      // 目標值小于中值，則中間右側可以拋棄了
      right = mid - 1;
    }
  }
  return -1;
};

三、寫在最后

本文是二分查找-模版 I 的最后一題，你會發現這道題的難度確實提升了，但仔細分析，借助自己的寫寫畫畫，仍然可以找到模版I的影子，加油！

如果對你有所幫助不妨給本專案的github 點個 star，這是對我最大的鼓勵～

關于我

花名：余光
WX：j565017805
沉迷 JS，水平有限，虛心學習中

其他沉淀

JavaScript 版 LeetCode 題解
前端進階筆記
CSDN

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/233632.html

標籤：其他

上一篇：【雷雨佳的個人介紹】

下一篇：PYTHON小白請教sys.exit(app.exec_())如何與其他while 回圈并存？

LeetCode題解：搜索旋轉排序陣列

搜索旋轉排序陣列（middle）

一、題目

二、二分法解題

三、寫在最后