快速业务通道

找到数组轮转的X

作者 佚名技术 来源 程序设计 浏览 发布时间 2012-06-29

问题:用C++代码实现函数 FindSortedArrayRotation。该函数接受一个整数数组和数组的长度。这个整数数组本来是有序的(升序),但被轮转了X位置(对给定的整数X (0 <= X <= (arrayLength - 1)),数组的每个元素向前移动X位置,也就是array[i]移动到array[(i+X)%arrayLength]。请实现FindSortedArrayRotation,找出X。要求时间必须小于O(n)

参考代码:

以下为引用的内容:

int FindSortedArrayRotation(int *array, int arrayLength)
{
  // Insert your implementation here
  /* 
After rotation the array was divided into 2 parts: array[0…x-1] and array[x…arrayLength-1]. And each part is sorted in ascending order. But array[x-1]>array[x]. This is a turn corner. My idea is use binary_search algorithm to find the turn corner.
Running time is O(log(2)).
*/
int left = 0;
int right = arrayLength – 1;
if(array[left]<= array[right]) return 0;
while(left<=right)
{
int middle = (left+right)/2;
if(array[middle -1] > array[middle]) return middle;
if(array[middle] > array[right]) left = middle + 1;
else right = middle -1;
}
return -1;
}

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务,公司网站:http://www.lingzhong.cn 为了给广大客户了解更多的技术信息,本技术文章收集来源于网络,凌众科技尊重文章作者的版权,如果有涉及你的版权有必要删除你的文章,请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息,谢谢!

分享到: 更多

Copyright ©1999-2011 厦门凌众科技有限公司 厦门优通互联科技开发有限公司 All rights reserved

地址(ADD):厦门软件园二期望海路63号701E(东南融通旁) 邮编(ZIP):361008

电话:0592-5908028 传真:0592-5908039 咨询信箱:web@lingzhong.cn 咨询OICQ:173723134

《中华人民共和国增值电信业务经营许可证》闽B2-20100024  ICP备案:闽ICP备05037997号