在循环排序数组中搜索元素

发布于 2024-09-01 17:12:57 字数 1767 浏览 7 评论 0原文

我们希望在循环排序数组中搜索给定元素,其复杂度不大于O(log n)
示例:在 {5,9,13,1,3} 中搜索 13

我的想法是将循环数组转换为常规排序数组,然后对结果数组进行二分搜索,但我的问题是我提出的算法很愚蠢,它需要 O(n)最坏的情况:

for(i = 1; i < a.length; i++){
    if (a[i] < a[i-1]){
        minIndex = i; break;
    }
}

那么第 i 个元素对应的索引将根据以下关系确定:

(i + minInex - 1) % a.length

很明显,我的转换(从循环到常规)算法可能需要 O(n),因此我们需要一个更好的算法。

根据 ire_and_curses 的想法,这是 Java 中的解决方案:

public int circularArraySearch(int[] a, int low, int high, int x){
    //instead of using the division op. (which surprisingly fails on big numbers)
    //we will use the unsigned right shift to get the average
    int mid = (low + high) >>> 1;
    if(a[mid] == x){
        return mid;
    }
    //a variable to indicate which half is sorted
    //1 for left, 2 for right
    int sortedHalf = 0;
    if(a[low] <= a[mid]){
        //the left half is sorted
        sortedHalf = 1;
        if(x <= a[mid] && x >= a[low]){
            //the element is in this half
            return binarySearch(a, low, mid, x);
        }
    }
    if(a[mid] <= a[high]){
        //the right half is sorted
        sortedHalf = 2;
        if(x >= a[mid] && x<= a[high] ){
            return binarySearch(a, mid, high, x);
        }
    }
    // repeat the process on the unsorted half
    if(sortedHalf == 1){
        //left is sorted, repeat the process on the right one
        return circularArraySearch(a, mid, high, x);
    }else{
        //right is sorted, repeat the process on the left
        return circularArraySearch(a, low, mid, x);
    }
}

希望这会起作用。

We want to search for a given element in a circular sorted array in complexity not greater than O(log n).
Example: Search for 13 in {5,9,13,1,3}.

My idea was to convert the circular array into a regular sorted array then do a binary search on the resulting array, but my problem was the algorithm I came up was stupid that it takes O(n) in the worst case:

for(i = 1; i < a.length; i++){
    if (a[i] < a[i-1]){
        minIndex = i; break;
    }
}

then the corresponding index of ith element will be determined from the following relation:

(i + minInex - 1) % a.length

it is clear that my conversion (from circular to regular) algorithm may take O(n), so we need a better one.

According to ire_and_curses idea, here is the solution in Java:

public int circularArraySearch(int[] a, int low, int high, int x){
    //instead of using the division op. (which surprisingly fails on big numbers)
    //we will use the unsigned right shift to get the average
    int mid = (low + high) >>> 1;
    if(a[mid] == x){
        return mid;
    }
    //a variable to indicate which half is sorted
    //1 for left, 2 for right
    int sortedHalf = 0;
    if(a[low] <= a[mid]){
        //the left half is sorted
        sortedHalf = 1;
        if(x <= a[mid] && x >= a[low]){
            //the element is in this half
            return binarySearch(a, low, mid, x);
        }
    }
    if(a[mid] <= a[high]){
        //the right half is sorted
        sortedHalf = 2;
        if(x >= a[mid] && x<= a[high] ){
            return binarySearch(a, mid, high, x);
        }
    }
    // repeat the process on the unsorted half
    if(sortedHalf == 1){
        //left is sorted, repeat the process on the right one
        return circularArraySearch(a, mid, high, x);
    }else{
        //right is sorted, repeat the process on the left
        return circularArraySearch(a, low, mid, x);
    }
}

Hopefully this will work.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(16

千年*琉璃梦 2024-09-08 17:12:58

下面是使用二分搜索的 C 实现。

int rotated_sorted_array_search(int arr[], int low, int high, int target)
{
    while(low<=high)
    {
        int mid = (low+high)/2;

        if(target == arr[mid])
            return mid;

        if(arr[low] <= arr[mid])
        {
            if(arr[low]<=target && target < arr[mid])
            {
                high = mid-1;
            }
            else
                low = mid+1;
        }
        else
        {
            if(arr[mid]< target && target <=arr[high])
            {
                low = mid+1;
            }
            else
                high = mid-1;
        }
    }
    return -1;
}

Below is a implementation in C using binary search.

int rotated_sorted_array_search(int arr[], int low, int high, int target)
{
    while(low<=high)
    {
        int mid = (low+high)/2;

        if(target == arr[mid])
            return mid;

        if(arr[low] <= arr[mid])
        {
            if(arr[low]<=target && target < arr[mid])
            {
                high = mid-1;
            }
            else
                low = mid+1;
        }
        else
        {
            if(arr[mid]< target && target <=arr[high])
            {
                low = mid+1;
            }
            else
                high = mid-1;
        }
    }
    return -1;
}
伏妖词 2024-09-08 17:12:58

这是 javascript 中的解决方案。用几个不同的阵列对其进行了测试,它似乎有效。它基本上使用 ire_and_curses 描述的相同方法:

function search(array, query, left, right) {
  if (left > right) {
    return -1;
  }

  var midpoint = Math.floor((left + right) / 2);
  var val = array[midpoint];
  if(val == query) {
    return midpoint;
  }

  // Look in left half if it is sorted and value is in that 
  // range, or if right side is sorted and it isn't in that range.
  if((array[left] < array[midpoint] && query >= array[left] && query <= array[midpoint])
    || (array[midpoint] < array[right] 
        && !(query >= array[midpoint] && query <= array[right]))) {
    return search(array, query, left, midpoint - 1);
  } else {
    return search(array, query, midpoint + 1, right);
  }
}

Here's a solution in javascript. Tested it with a few different arrays and it seems to work. It basically uses the same method described by ire_and_curses:

function search(array, query, left, right) {
  if (left > right) {
    return -1;
  }

  var midpoint = Math.floor((left + right) / 2);
  var val = array[midpoint];
  if(val == query) {
    return midpoint;
  }

  // Look in left half if it is sorted and value is in that 
  // range, or if right side is sorted and it isn't in that range.
  if((array[left] < array[midpoint] && query >= array[left] && query <= array[midpoint])
    || (array[midpoint] < array[right] 
        && !(query >= array[midpoint] && query <= array[right]))) {
    return search(array, query, left, midpoint - 1);
  } else {
    return search(array, query, midpoint + 1, right);
  }
}
顾铮苏瑾 2024-09-08 17:12:58

简单的二分查找,稍加改动。

旋转数组的索引=(i+pivot)%大小

pivot是索引i+1,其中a[i]>a[i+1]。

#include <stdio.h>
#define size 5
#define k 3
#define value 13
int binary_search(int l,int h,int arr[]){

int mid=(l+h)/2;

if(arr[(mid+k)%size]==value)
    return (mid+k)%size;

if(arr[(mid+k)%size]<value)
    binary_search(mid+1,h,arr);
else
    binary_search(l,mid,arr);
}

int main() {
    int arr[]={5,9,13,1,3};
    printf("found at: %d\n", binary_search(0,4,arr));
    return 0;
}

Simple binary search with a little change.

Index of rotating array= (i+pivot)%size

pivot is the index i+1 where a[i]>a[i+1].

#include <stdio.h>
#define size 5
#define k 3
#define value 13
int binary_search(int l,int h,int arr[]){

int mid=(l+h)/2;

if(arr[(mid+k)%size]==value)
    return (mid+k)%size;

if(arr[(mid+k)%size]<value)
    binary_search(mid+1,h,arr);
else
    binary_search(l,mid,arr);
}

int main() {
    int arr[]={5,9,13,1,3};
    printf("found at: %d\n", binary_search(0,4,arr));
    return 0;
}
赴月观长安 2024-09-08 17:12:58

Ruby 中的一个简单方法

def CircularArraySearch(a, x)
  low = 0
  high = (a.size) -1

  while low <= high
    mid = (low+high)/2
    if a[mid] == x
      return mid
    end
    if a[mid] <= a[high]
      if (x > a[mid]) && (x <= a[high])
        low = mid + 1
      elsif high = mid -1
      end
    else
      if (a[low] <= x) && (x < a[mid])
        high = mid -1
      else
        low = mid +1
      end
    end
  end
  return -1
end

a = [12, 14, 18, 2, 3, 6, 8, 9]
x = gets.to_i
p CircularArraySearch(a, x)

A simple method in Ruby

def CircularArraySearch(a, x)
  low = 0
  high = (a.size) -1

  while low <= high
    mid = (low+high)/2
    if a[mid] == x
      return mid
    end
    if a[mid] <= a[high]
      if (x > a[mid]) && (x <= a[high])
        low = mid + 1
      elsif high = mid -1
      end
    else
      if (a[low] <= x) && (x < a[mid])
        high = mid -1
      else
        low = mid +1
      end
    end
  end
  return -1
end

a = [12, 14, 18, 2, 3, 6, 8, 9]
x = gets.to_i
p CircularArraySearch(a, x)
猫卆 2024-09-08 17:12:58

虽然批准的答案是最佳的,但我们也可以使用类似且更清晰的算法。

  1. 运行二分搜索来查找枢轴元素(数组旋转的位置)。 O(logn)
  2. 枢轴的左半部分将按降序排序,在此处运行向后二分搜索来查找键。 O(logn)
  3. 枢轴的右半部分将按升序排序,在这半部分中运行正向二分搜索来查找键。 O(logn)
  4. 返回第 2 步和第 3 步中找到的关键索引。

总时间复杂度:O(logn)

欢迎思考。

Though approved answer is optimal but we can also do with a similar and cleaner algorithm.

  1. run a binary search to find pivot element (where the array is rotated). O(logn)
  2. left half of the pivot will be sorted in decreasing order, run a backward binary search here for the key. O(logn)
  3. right half of the pivot will be sorted in increasing order, run a forward binary search in this half for the key. O(logn)
  4. return found key index from step 2 and 3.

Total Time Complexity: O(logn)

Thoughts welcome.

梦里人 2024-09-08 17:12:58

guirgis:发布面试问题很蹩脚,猜猜你没有得到这份工作:-(

使用特殊的 cmp 函数,你只需要常规二分搜索一次。类似于:

def rotatedcmp(x, y):
  if x and y < a[0]:
    return cmp(x, y)
  elif x and y >= a[0]:
    return cmp(x, y)
  elif x < a[0]:
    return x is greater
  else:
    return y is greater

如果你可以依赖 int 下溢减去 a [0] - 访问每个元素时的 MIN_INT 并使用常规比较。

guirgis: It is lame to post an interview question, guess you didn't get the job :-(

Use a special cmp function and you need only one pass with regular binary search. Something like:

def rotatedcmp(x, y):
  if x and y < a[0]:
    return cmp(x, y)
  elif x and y >= a[0]:
    return cmp(x, y)
  elif x < a[0]:
    return x is greater
  else:
    return y is greater

If you can depend on int underflow subtract a[0] - MIN_INT from each element as it is accessed and use regular compare.

十二 2024-09-08 17:12:57

您可以通过利用数组已排序这一事实来实现此目的,但主值及其邻居值之一的特殊情况除外。

  • 求数组a的中间值。
  • 如果a[0] < a[mid],则所有值
    数组的前半部分是
    已排序。
  • 如果a[mid] < a[最后],然后是所有
    下半年的数值
    数组已排序。
  • 取已排序的
    一半,然后检查你的值是否
    位于其中(与
    那一半的最大 idx)。
  • 如果是这样,只需二进制
    搜索那一半。
  • 如果没有的话,它
    必须在未排序的一半中。拿
    那一半并重复这个过程,
    确定那一半的哪一半
    已排序等

You can do this by taking advantage of the fact that the array is sorted, except for the special case of the pivot value and one of its neighbours.

  • Find the middle value of the array a.
  • If a[0] < a[mid], then all values in
    the first half of the array are
    sorted.
  • If a[mid] < a[last], then all
    values in the second half of the
    array are sorted.
  • Take the sorted
    half, and check whether your value
    lies within it (compare to the
    maximum idx in that half).
  • If so, just binary
    search that half.
  • If it doesn't, it
    must be in the unsorted half. Take
    that half and repeat this process,
    determining which half of that half
    is sorted, etc.
风吹短裙飘 2024-09-08 17:12:57

不是很优雅,但最重要的是 - 只需使用二分搜索来找到旋转数组的主元,然后再次执行二分搜索,补偿主元的偏移量。执行两次完整搜索有点愚蠢,但它确实满足条件,因为 O(log n) + O(log n) == O(log n)。保持简单和愚蠢(tm)!

Not very elegant, but of the top off my head - just use binary search to find the pivot of the rotated array, and then perform binary search again, compensating for the offset of the pivot. Kind of silly to perform two full searches, but it does fulfill the condition, since O(log n) + O(log n) == O(log n). Keep it simple and stupid(tm)!

随梦而飞# 2024-09-08 17:12:57

这是一个在 Java 中运行的示例。由于这是一个排序数组,因此您可以利用它并运行二分搜索,但是需要对其进行稍微修改以适应枢轴的位置。

该方法如下所示:

private static int circularBinSearch ( int key, int low, int high )
{
    if (low > high)
    {
        return -1; // not found
    }

    int mid = (low + high) / 2;
    steps++;

    if (A[mid] == key)
    {
        return mid;
    }
    else if (key < A[mid])
    {
        return ((A[low] <= A[mid]) && (A[low] > key)) ?
               circularBinSearch(key, mid + 1, high) :
               circularBinSearch(key, low, mid - 1);
    }
    else // key > A[mid]
    {
        return ((A[mid] <= A[high]) && (key > A[high])) ?
               circularBinSearch(key, low, mid - 1) :
               circularBinSearch(key, mid + 1, high);
    }
}

现在为了缓解任何担忧,这里有一个很好的小类来验证算法:

public class CircularSortedArray
{
    public static final int[] A = {23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 
                                   91, 99, 1, 4, 11, 14, 15, 17, 19};
    static int steps;

    // ---- Private methods ------------------------------------------

    private static int circularBinSearch ( int key, int low, int high )
    {
        ... copy from above ...
    }

    private static void find ( int key )
    {
        steps = 0;
        int index = circularBinSearch(key, 0, A.length-1);
        System.out.printf("key %4d found at index %2d in %d steps\n",
                          key, index, steps);
    }

    // ---- Static main -----------------------------------------------

    public static void main ( String[] args )
    {
        System.out.println("A = " + Arrays.toString(A));
        find(44);   // should not be found
        find(230);
        find(-123);

        for (int key: A)  // should be found at pos 0..18
        {
            find(key);
        }
    }
}

它会给您一个输出:

A = [23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 91, 99, 1, 4, 11, 14, 15, 17, 19]
key   44 found at index -1 in 4 steps
key  230 found at index -1 in 4 steps
key -123 found at index -1 in 5 steps
key   23 found at index  0 in 4 steps
key   27 found at index  1 in 3 steps
key   29 found at index  2 in 4 steps
key   31 found at index  3 in 5 steps
key   37 found at index  4 in 2 steps
key   43 found at index  5 in 4 steps
key   49 found at index  6 in 3 steps
key   56 found at index  7 in 4 steps
key   64 found at index  8 in 5 steps
key   78 found at index  9 in 1 steps
key   91 found at index 10 in 4 steps
key   99 found at index 11 in 3 steps
key    1 found at index 12 in 4 steps
key    4 found at index 13 in 5 steps
key   11 found at index 14 in 2 steps
key   14 found at index 15 in 4 steps
key   15 found at index 16 in 3 steps
key   17 found at index 17 in 4 steps
key   19 found at index 18 in 5 steps

This is an example that works in Java. Since this is a sorted array you take advantage of this and run a Binary Search, however it needs to be slightly modified to cater for the position of the pivot.

The method looks like this:

private static int circularBinSearch ( int key, int low, int high )
{
    if (low > high)
    {
        return -1; // not found
    }

    int mid = (low + high) / 2;
    steps++;

    if (A[mid] == key)
    {
        return mid;
    }
    else if (key < A[mid])
    {
        return ((A[low] <= A[mid]) && (A[low] > key)) ?
               circularBinSearch(key, mid + 1, high) :
               circularBinSearch(key, low, mid - 1);
    }
    else // key > A[mid]
    {
        return ((A[mid] <= A[high]) && (key > A[high])) ?
               circularBinSearch(key, low, mid - 1) :
               circularBinSearch(key, mid + 1, high);
    }
}

Now to ease any worries, here's a nice little class that verifies the algorithm:

public class CircularSortedArray
{
    public static final int[] A = {23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 
                                   91, 99, 1, 4, 11, 14, 15, 17, 19};
    static int steps;

    // ---- Private methods ------------------------------------------

    private static int circularBinSearch ( int key, int low, int high )
    {
        ... copy from above ...
    }

    private static void find ( int key )
    {
        steps = 0;
        int index = circularBinSearch(key, 0, A.length-1);
        System.out.printf("key %4d found at index %2d in %d steps\n",
                          key, index, steps);
    }

    // ---- Static main -----------------------------------------------

    public static void main ( String[] args )
    {
        System.out.println("A = " + Arrays.toString(A));
        find(44);   // should not be found
        find(230);
        find(-123);

        for (int key: A)  // should be found at pos 0..18
        {
            find(key);
        }
    }
}

That give you an output of:

A = [23, 27, 29, 31, 37, 43, 49, 56, 64, 78, 91, 99, 1, 4, 11, 14, 15, 17, 19]
key   44 found at index -1 in 4 steps
key  230 found at index -1 in 4 steps
key -123 found at index -1 in 5 steps
key   23 found at index  0 in 4 steps
key   27 found at index  1 in 3 steps
key   29 found at index  2 in 4 steps
key   31 found at index  3 in 5 steps
key   37 found at index  4 in 2 steps
key   43 found at index  5 in 4 steps
key   49 found at index  6 in 3 steps
key   56 found at index  7 in 4 steps
key   64 found at index  8 in 5 steps
key   78 found at index  9 in 1 steps
key   91 found at index 10 in 4 steps
key   99 found at index 11 in 3 steps
key    1 found at index 12 in 4 steps
key    4 found at index 13 in 5 steps
key   11 found at index 14 in 2 steps
key   14 found at index 15 in 4 steps
key   15 found at index 16 in 3 steps
key   17 found at index 17 in 4 steps
key   19 found at index 18 in 5 steps
痴情换悲伤 2024-09-08 17:12:57

您有三个值:lmh,分别表示搜索的低、中、高索引值。如果您认为您会继续搜索每种可能性:

// normal binary search
l < t < m    - search(t,l,m)
m < t < h    - search(t,m,h)

// search over a boundary
l > m, t < m - search(t,l,m)
l > m, t > l - search(t,l,m)
m > h, t > m - search(t,m,h)  
m > h, t < h - search(t,m,h)  

这是一个考虑目标值可能在哪里并搜索那一半空间的问题。最多一半的空间会有包裹,很容易判断目标值是在一半还是另一半。

这是一个元问题 - 您是否认为二分搜索通常是如何呈现的 - 查找两点之间的值,或者更一般地说,作为抽象搜索空间的重复划分。

You have three values, l,m,h for the values at the low, mid and high indexes of your search. If you think were you would continue searching for each possibility:

// normal binary search
l < t < m    - search(t,l,m)
m < t < h    - search(t,m,h)

// search over a boundary
l > m, t < m - search(t,l,m)
l > m, t > l - search(t,l,m)
m > h, t > m - search(t,m,h)  
m > h, t < h - search(t,m,h)  

It's a question of considering where the target value could be, and searching that half of the space. At most one half of the space will have the wrap-over in it, and it is easy to determine whether or not the target value is in that half or the other.

It's sort of a meta question - do you think of binary search it terms of how it is often presented - finding a value between two points, or more generally as a repeated division of an abstract search space.

谁把谁当真 2024-09-08 17:12:57

您可以使用二分查找来查找最小元素的位置并将其减少到O(Log n)

您可以通过以下方式找到位置(这只是算法的草图,它不准确,但您可以从中得到想法):
1. i <- 1
2. j <- n
3. 当我< j
3.1. k <- (ji) / 2
3.2.如果 arr[k] < arr[i] 则 j <- k
3.3. else i <- k

找到最小元素的位置后,您可以将数组视为两个排序数组。

You can use binary search to find the location of smallest element and reduce it to O(Log n).

You can find the location by (this is just a sketch of algorithm, it's inaccurate but you can get the idea from it):
1. i <- 1
2. j <- n
3. while i < j
3.1. k <- (j-i) / 2
3.2. if arr[k] < arr[i] then j <- k
3.3. else i <- k

After finding the location of the smallest element you can treat the array as two sorted arrays.

相守太难 2024-09-08 17:12:57

您只需使用简单的二分搜索,就像它是常规排序数组一样。唯一的技巧是您需要旋转数组索引:

(index + start-index) mod array-size

其中起始索引是循环数组中第一个元素的偏移量。

You just use a simple binary search as if it were a regular sorted array. The only trick is you need to rotate the array indexes:

(index + start-index) mod array-size

where the start-index is the offset of the first element in the circular array.

不即不离 2024-09-08 17:12:57
public static int _search(int[] buff, int query){
    int s = 0;
    int e = buff.length;
    int m = 0; 

    while(e-s>1){
        m = (s+e)/2;
        if(buff[offset(m)] == query){
            return offset(m);
        } else if(query < buff[offset(m)]){
            e = m;
        } else{
            s = m;
        }
    }

    if(buff[offset(end)]==query) return end;
    if(buff[offset(start)]==query) return start;
    return -1;
}

public static int offset(int j){
    return (dip+j) % N;
}
public static int _search(int[] buff, int query){
    int s = 0;
    int e = buff.length;
    int m = 0; 

    while(e-s>1){
        m = (s+e)/2;
        if(buff[offset(m)] == query){
            return offset(m);
        } else if(query < buff[offset(m)]){
            e = m;
        } else{
            s = m;
        }
    }

    if(buff[offset(end)]==query) return end;
    if(buff[offset(start)]==query) return start;
    return -1;
}

public static int offset(int j){
    return (dip+j) % N;
}
酒几许 2024-09-08 17:12:57

检查这个coe,

    def findkey():
    key = 3

    A=[10,11,12,13,14,1,2,3]
    l=0
    h=len(A)-1
    while True:
        mid = l + (h-l)/2
        if A[mid] == key:
            return mid
        if A[l] == key:
            return l
        if A[h] == key:
            return h
        if A[l] < A[mid]:
            if key < A[mid] and key > A[l]:
                h = mid - 1
            else:
                l = mid + 1
        elif A[mid] < A[h]:
            if key > A[mid] and key < A[h]:
                l = mid + 1
            else:
                h = mid - 1

if __name__ == '__main__':
    print findkey()

Check this coe,

    def findkey():
    key = 3

    A=[10,11,12,13,14,1,2,3]
    l=0
    h=len(A)-1
    while True:
        mid = l + (h-l)/2
        if A[mid] == key:
            return mid
        if A[l] == key:
            return l
        if A[h] == key:
            return h
        if A[l] < A[mid]:
            if key < A[mid] and key > A[l]:
                h = mid - 1
            else:
                l = mid + 1
        elif A[mid] < A[h]:
            if key > A[mid] and key < A[h]:
                l = mid + 1
            else:
                h = mid - 1

if __name__ == '__main__':
    print findkey()
诗笺 2024-09-08 17:12:57

这是一个与二分搜索相关的想法。只需继续备份右数组索引边界的索引,左索引边界存储在步长中:

step = n
pos = n
while( step > 0 ):
    test_idx = pos - step   #back up your current position
    if arr[test_idx-1] < arr[pos-1]:
        pos = test_idx
    if (pos == 1) break
    step /= 2 #floor integer division
return arr[pos]

为了避免 (pos==1) 的情况,我们可以循环备份(进入负数)并采取 ( pos-1) 模 n。

Here is an idea, related to binary search. Just keep backing up your index for the right array-index bound, the left index bound is stored in the step size:

step = n
pos = n
while( step > 0 ):
    test_idx = pos - step   #back up your current position
    if arr[test_idx-1] < arr[pos-1]:
        pos = test_idx
    if (pos == 1) break
    step /= 2 #floor integer division
return arr[pos]

To avoid the (pos==1) thing, we could back up circularly (go into negative numbers) and take (pos-1) mod n.

愁杀 2024-09-08 17:12:57

我认为您可以使用以下代码找到偏移量:

public static int findOffset(int [] arr){
        return findOffset(arr,0,arr.length-1);
    }
private static int findOffset(int[] arr, int start, int end) {

    if(arr[start]<arr[end]){
        return -1;
    }
    if(end-start==1){
        return end;
    }
    int mid = start + ((end-start)/2);
    if(arr[mid]<arr[start]){
        return findOffset(arr,start,mid);
    }else return findOffset(arr,mid,end);
}

I think you can find the offset using this code:

public static int findOffset(int [] arr){
        return findOffset(arr,0,arr.length-1);
    }
private static int findOffset(int[] arr, int start, int end) {

    if(arr[start]<arr[end]){
        return -1;
    }
    if(end-start==1){
        return end;
    }
    int mid = start + ((end-start)/2);
    if(arr[mid]<arr[start]){
        return findOffset(arr,start,mid);
    }else return findOffset(arr,mid,end);
}
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文