有序數(shù)列的旋轉(zhuǎn)
現(xiàn)在待查數(shù)組不再是一個單純的有序數(shù)列了淆九，而是先把它在某個位置截為兩段劲蜻，然后交換前后兩段的順序佳谦，形成新的數(shù)列戴涝。之后，再在這個新數(shù)列中進(jìn)行查找钻蔑。
比如：我們有一個原本的數(shù)列 [3, 5, 9, 7, 12, 15, 18, 32, 66, 78, 94, 103, 269]，先把它截為兩段：[3, 5, 9, 7, 12, 15, 18, 32]和[66, 78, 94, 103, 269]奸鸯；然后把這兩個子數(shù)列前后交換咪笑，重新銜接成一個新的數(shù)列： [66, 78, 94, 103, 269，3, 5, 9, 7, 12, 15, 18, 32]娄涩；之后我們在新數(shù)列中查找目標(biāo)數(shù)窗怒。
無重復(fù)數(shù)的旋轉(zhuǎn)數(shù)列的二分查找
套用經(jīng)典二分查找
旋轉(zhuǎn)數(shù)列當(dāng)然也分為含重復(fù)數(shù)的，和不含重復(fù)數(shù)的蓄拣。我們先來看看相對簡單一些的扬虚，沒有重復(fù)元素的情況。
無重復(fù)數(shù)旋轉(zhuǎn)數(shù)列的查找球恤，基本思想還是按照二分查找那樣辜昵，整體是一個迭代算法，每次迭代都對應(yīng)一個待查區(qū)間咽斧。
每次迭代所面對的待查區(qū)間堪置，實際上可能有下面三種情況：
上圖中的橘色線段表示一個數(shù)字序列（雖然實際上我們的序列應(yīng)該是分布在一條直線上的若干離散點躬存，而且未必均勻分布，但是為了看得清楚舀锨，我們暫且用一條線段代替）岭洲。
【case-iii】是一個完全的有序數(shù)列，而【case-i】和【case-ii】則是旋轉(zhuǎn)有序的數(shù)列坎匿。
假設(shè)整個旋轉(zhuǎn)數(shù)列是用arr表示的遞增序列的旋轉(zhuǎn)盾剩，low和high用于指定其待查區(qū)域的起始點下標(biāo)。那么:
