给定一个旋转了任意次的有序数组A和一个数n,实现一个O(logn)的算法返回n在A中的下标,若没有返回-1。(假定原有序数组是递增的)
例子:
输入:A:15,16,19,20,25,1,3,4,5,7,10,14;n:5
输出:8
思路:
有序数组旋转之后,前半部分仍是有序的,后半部分无序,仍然可以用二分的思想。
如果a[mid] == n,结束。
如果a[mid] > n,有两种情况:
1、如果a[mid] > a[left],说明前半段有序:那么如果a[left] > n则n在后半段,否则在前半段;
2、如果a[mid] < a[left],说明后半段有序:那么n在前半段。
如果a[mid] < n......
阅读全文