疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

在旋转有序数组内找特定的值


 

  要求

  给定一没有重复元素的旋转数组(它对应的原数组是有序的),求给定元素在旋转数组内的下标(不存在的返回-1)。

  例如

  有序数组为{0,1,2,4,5,6,7},它的一个旋转数组为{4,5,6,7,0,1,2}.

  元素6在旋转数组内,返回2

  元素3不在旋转数组内,返回-1

  分析

  遍历一遍,可以轻松搞定,时间复杂度为O(n),因为是有序数组旋转得到,这样做肯定不是最优解。有序,本能反映用二分查找,举个例子看看特点

  可以看出中间位置两段起码有一个是有序的(不是左边,就是右边),那么就可以在有序的范围内使用二分查找;如果不再有序范围内,就到另一半去找。

  参考代码

  int search(int A[], int n, int target) {

  int beg = 0;

  int end = n - 1;

  while (beg <= end)

  {

  int mid = beg + (end - beg) / 2;

  if(A[mid] == target)

  return mid;

  if(A[beg] <= A[mid])

  {

  if(A[beg] <= target && target < A[mid])

  end = mid - 1;

  else

  beg = mid + 1;

  }

  else

  {

  if(A[mid] < target && target <= A[end])

  beg = mid + 1;

  else

  end = mid - 1;

  }

  }

  return -1;

  }

  复制代码

  扩展

  上边的有求是没有重复的元素,现在稍微扩展下,可以有重复的元素,其他的要求不变。

  思路

  大致思路与原来相同,这是需要比较A[beg] 与 A[mid]的关系

  A[beg] < A[mid] ----左边有序

  A[beg] > A[mid] ----右边有序

  A[beg] = A[mid] ----++beg

  复制代码

  bool search(int A[], int n, int target) {

  int beg = 0;

  int end = n - 1;

  while (beg <= end)

  {

  int mid = beg + (end - beg) / 2;

  if(A[mid] == target)

  return true;

  if(A[beg] < A[mid])

  {