旋轉(zhuǎn)數(shù)組中查找數(shù)字

• 如題所示：
• 思路
• 源代碼如下：

如題所示：

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點上進(jìn)行了旋轉(zhuǎn)。
( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
搜索一個給定的目標(biāo)值，如果數(shù)組中存在這個目標(biāo)值，則返回它的索引，否則返回 -1 。
你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
你的算法時間復(fù)雜度必須是 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

思路

?首先，如果nums[mid] == target，那么找到目標(biāo)元素，返回mid
?如果nums[l] < nums[r]，說明l~r范圍的元素有序，那么執(zhí)行正常的二分查找
?否則，根據(jù)mid位置的值判斷mid是在左半部分還是右半部分
–如果nums[mid] ≥ nums[l]，說明mid在左半部分
?當(dāng)target > nums[r] && target < nums[mid]，那么target只可能出現(xiàn)在mid的左邊，因此在mid左邊繼續(xù)查找
?否則，target只可能出現(xiàn)在mi

總結(jié)

以上是生活随笔為你收集整理的旋转数组中查找数字的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。