【題目描述】
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è)有一個(gè)排序的按未知的旋轉(zhuǎn)軸旋轉(zhuǎn)的數(shù)組(比如，0 1 2 4 5 6 7 可能成為4 5 6 7 0 1 2)。給定一個(gè)目標(biāo)值進(jìn)行搜索，如果在數(shù)組中找到目標(biāo)值返回?cái)?shù)組中的索引位置，否則返回-1。你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
【題目鏈接】
www.lintcode.com/en/problem/search-in-rotated-sorted-array/
【題目解析】
如果沒(méi)有重復(fù)元素，就是二分搜索，mid要么落在大元素的區(qū)間，要么落在小元素的區(qū)間。先看mid落在前半?yún)^(qū)間還是后半?yún)^(qū)間，再看target是在該區(qū)間的前半部分還是后半部分。
【參考答案】
