题意
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。...所以数组的情况应该是这样的:
?
对不起,我画得有些抽象,但是精髓传达到了。什么意思呢?就是原本升序的数组分成了两截之后交换顺序,那么现在的数组应该是两端递增的序列拼接构成的。...我们再来分析一下二分时候可能出现的情况,一开始的时候l在最左侧,r在最右侧,m则是两侧都有可能。如果m在左侧部分,那么m位置的值一定大于l,否则一定小于l。...所以我们通过比较m和l位置元素的大小关系可以判断m在左侧还是右侧。
如果说我们最终的搜索目标是寻找左侧部分的最大值,那么当m处的值大于l时,则舍弃左侧部分,因为左侧部分已经不可能是答案了。...这是一种情况,即m的位置在断点右侧,也就是右侧。那么我们通过判断target和l处的大小关系可以判断target可能在哪个部分。