T33. Search in Rotated Sorted Array【Medium】
題目
假設(shè)有一個升序的數(shù)組以某個未知的支點旋轉(zhuǎn)袜蚕。
（例如塞祈，0 1 2 3 4 5 6 7 可以變成 4 5 6 7 0 1 2）
假設(shè)這個數(shù)組中沒有重復的元素，給你一個 target(目標數(shù))，如果在這個數(shù)組中找到則返回它的 index，如果找不到就返回 -1
思路
首先，一般的有序的數(shù)組众旗，查找一個數(shù)字一般都是用二分法，因為這樣比較有效率趟畏。
按題中說法旋轉(zhuǎn)數(shù)組后贡歧，分成的兩半仍然是排好序的數(shù)組。
例如赋秀，4 5 6 7 0 1 2艘款，左邊的 4 5 6 7，以及右邊的 0 1 2 都是排好序的沃琅，可以先確定 target 在哪邊哗咆，然后繼續(xù)二分查找。不過這個代碼是從中間二分益眉，分到的一半可能還是有兩段排序的代碼晌柬，需要繼續(xù)分，就是很神奇的代碼郭脂。
具體看代碼以及注釋~還是這句話年碘，最好自己拿個例子試試，瞬間清晰展鸡！
信我 (? ??_??)? 屿衅！
代碼
代碼取自 Top Solution，稍作注釋
public int search(int[] nums, int target) {
//定位數(shù)組頭和尾
int start = 0;
int end = nums.length - 1;
//start > end時表示里面不包含了莹弊，跳出循環(huán)
while (start <= end){
int mid = (start + end) / 2;
//找到匹配值涤久，返回index
if (nums[mid] == target)
return mid;
//通過nums[start] <= nums[mid]表明start~mid這段是正確升序的
if (nums[start] <= nums[mid]){
//這就是二分法的做法涡尘，判斷點在哪里，然后通過把start或者end賦予新的mid左右的值响迂，表示選擇前一段或者后一段
if (target < nums[mid] && target >= nums[start])
end = mid - 1;
else
start = mid + 1;
}
//通過nums[mid] <= nums[end]表明mid ~ end這段是正確升序的
if (nums[mid] <= nums[end]){
//這就是二分法的做法考抄，判斷點在哪里，然后通過把start或者end賦予新的mid左右的值蔗彤，表示選擇前一段或者后一段
if (target > nums[mid] && target <= nums[end])
start = mid + 1;
else
end = mid - 1;
}
}
//不存在的川梅，返回-1
return -1;
}
補充
注意啦~這里是代碼里的東西要補充說一下！一開始不明白這代碼為什么要這么多if然遏。
這里是有對應(yīng)關(guān)系的贫途，先判斷在 start~mid是升序的才能用 target < nums[mid] && target >= nums[start] ，來判斷 target 在不在這一段待侵，然后若不是才說是在 mid ~ end的丢早。（希望只有我一個人最開始第一眼沒有看出來 ╮(??? ????)╭...）
if (nums[start] <= nums[mid]){
if (target < nums[mid] && target >= nums[start])
end = mid - 1;
else
start = mid + 1
}
