【題目描述】
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 -1.You may assume no duplicate exists in the array.
假設有一個排序的按未知的旋轉軸旋轉的數(shù)組(比如，0 1 2 4 5 6 7 可能成為4 5 6 7 0 1 2)祖凫。給定一個目標值進行搜索燃异，如果在數(shù)組中找到目標值返回數(shù)組中的索引位置鸟款，否則返回-1雁刷。你可以假設數(shù)組中不存在重復的元素。
【題目鏈接】
www.lintcode.com/en/problem/search-in-rotated-sorted-array/
【題目解析】
如果沒有重復元素甩卓，就是二分搜索凌节，mid要么落在大元素的區(qū)間，要么落在小元素的區(qū)間亚隅。先看mid落在前半?yún)^(qū)間還是后半?yún)^(qū)間硼莽，再看target是在該區(qū)間的前半部分還是后半部分。
【參考答案】
