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.
解題思路：
題意為在旋轉數(shù)組中找出目標數(shù)，與找最小數(shù)http://www.kangry.net/blog/?type=article&article_id=111是兄弟題目。類似于2分查找，分析1下即可。
數(shù)組元素：XX XX... XX XX... XX
數(shù)組下標：start middle end
如上所示，
1、若middle等于目標值，返回middle，若start等于目標值，則返回start，若end等于目標值，則返回end。
2、若middle大于目標值，并且start小于目標值，表示start到middle是順序部份，且目標值肯定在start到middle部份（若存在的話），因此將end賦值為middle⑴
3、若middle小于目標值，并且end大于目標值，表示middle到end是順序部份，且目標值肯定在middle到end部份（若存在的話），因此將start賦值為middle+1
4、若middle大于目標值，并且start大于目標值，這要分情況討論。若start到middle不是順序部份，表明target在start到middle之間（若存在的話），否則在middle到end之間
5、若middle小于目標值，且end小于目標值，分情況討論，若middle到end不是順序部份，則target在middle到end之間（若存在的話），否則在start到middle之間。
下面是代碼：
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學習，原版權很多不明，如有侵權請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
