33. 搜索旋轉排序數組
- 2019 年 10 月 10 日
- 筆記
題目描述
假設按照升序排序的數組在預先未知的某個點上進行了旋轉。
( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。
搜索一個給定的目標值，如果數組中存在這個目標值，則返回它的索引，否則返回 -1 。
你可以假設數組中不存在重複的元素。
你的演算法時間複雜度必須是 O(log n) 級別。
示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0 輸出: 4
示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3 輸出: -1
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array 著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
思路
這是一個我在網上看到的前端頭條技術終面的一個演算法題。
題目要求時間複雜度為logn，因此基本就是二分法了。這道題目不是直接的有序數組，不然就是easy了。
首先要知道，我們隨便選擇一個點，將數組分為前後兩部分，其中一部分一定是有序的。
具體步驟：
- 我們可以先找出mid，然後根據mid來判斷，mid是在有序的部分還是無序的部分
假如mid小於start，則mid一定在右邊有序部分。假如mid大於等於start， 則mid一定在左邊有序部分。
注意等號的考慮
- 然後我們繼續判斷target在哪一部分， 我們就可以捨棄另一部分了
我們只需要比較target和有序部分的邊界關係就行了。比如mid在右側有序部分，即[mid, end] 那麼我們只需要判斷 target >= mid && target <= end 就能知道target在右側有序部分，我們就 可以捨棄左邊部分了(start = mid + 1)， 反之亦然。
我們以([6,7,8,1,2,3,4,5], 4)為例講解一下：
關鍵點解析
- 二分法
- 找出有序區間，然後根據target是否在有序區間捨棄一半元素
程式碼
- 語言支援: Javascript
/* * @lc app=leetcode id=33 lang=javascript * * [33] Search in Rotated Sorted Array */ /** * @param {number[]} nums * @param {number} target * @return {number} */ var search = function(nums, target) { // 時間複雜度：O(logn) // 空間複雜度：O(1) // [6,7,8,1,2,3,4,5] let start = 0; let end = nums.length - 1; while (start <= end) { const mid = start + ((end - start) >> 1); if (nums[mid] === target) return mid; // [start, mid]有序 // ️⚠️注意這裡的等號 if (nums[mid] >= nums[start]) { //target 在 [start, mid] 之間 // 其實target不可能等於nums[mid]， 但是為了對稱，我還是加上了等號 if (target >= nums[start] && target <= nums[mid]) { end = mid - 1; } else { //target 不在 [start, mid] 之間 start = mid + 1; } } else { // [mid, end]有序 // target 在 [mid, end] 之間 if (target >= nums[mid] && target <= nums[end]) { start = mid + 1; } else { // target 不在 [mid, end] 之間 end = mid - 1; } } } return -1; };