LeetCode Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return ⑴.

You may assume no duplicate exists in the array.

思路分析：這題一樣考察2分查找，但是是在rotation以后的數組中進行2分查找。這題的特點是，每次2分后，最少有1半是有序的，另外一半是無序的（遭到了rotation的影響）。所以要利用這1特性，通過比較target和有序的那半邊數組的最小數和最大數，來決定l和m的更新規則。具體而言

1.如果target = A[m] 返回m

2 如果target 不等于A[m]

2.1 如果A[m] < A[r],說明A[m...r]有序，沒有收到rotation影響，可以判斷target是不是在A[m...r]范圍內，如果是更新l=m+1;否則更新r=m⑴

2.2 如果A[m] >= A[r],說明A[l...m]有序，沒有收到rotation影響，可以判斷target是不是在A[l...m]范圍內，如果是更新r=m⑴;否則更新l=m+1

所以利用每次依然有序的半邊數組，我們依然可以進行2分查找，更新l和r，每次縮小1半的搜索范圍，時間復雜度O（log(n)），空間復雜度O（1），只有常數級別的額外空間。注意判斷target是不是在A[m...r]范圍和target是不是在A[l...m]范圍內的時候，要斟酌target == A[r]和target == A[l]的情況，2分查找的實現等號情況的斟酌要特別謹慎。

AC 時間：5min。

AC Code

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈