在java中搜索排序和旋转数组中的元素

Question

您将获得一个排序和旋转的数组，如下所示：

int arr[]={16,19,21,25,3,5,8,10};

如果您注意到数组已排序和旋转。您需要以 o(log n) 时间复杂度搜索上述数组中的元素。

Answer 1

您可以使用线性搜索在上述数组中搜索元素，但这需要 o(n)。
您可以使用二进制搜索算法的变体来解决上述问题。您可以使用可以将数组划分为两个排序的子数组（{16,19,21,25},{3,5,8,10} ）的属性，尽管您不需要找到枢轴点（元素开始减少）。

算法：

• 计算中，即低+高/2。
• 检查 a[mid…high] 是否已排序
• 如果数字介于范围之间，则低=中+1。
• 如果数字不在范围内，high=mid-1。
• 检查 a[low..mid] 是否已排序。
• 如果数字位于范围之间，则高 = 中 1..
• 如果数字不在范围内，则低=中+1。

让我们借助示例来理解这一点。

在上述数组中搜索 5 涉及的步骤：

• 计算中即 3 (0+7/2)
• amid > ahigh && 5 < alow && 5 < a[high] ( 25 )，所以数字( 5 )在右边，所以low会变成中+1。
• a[mid] == 5，所以你可以返回它。

用于在已排序和旋转的数组中搜索元素的 Java 程序：
创建一个名为的类

SearchElementSortedAndRotatedArrayMain.java。

package org.arpit.java2blog;
public class SearchElementSortedAndRotatedArrayMain {

    public static void main(String[] args) {
        int arr[]={16,19,21,25,3,5,8,10};
        System.out.println("Index of element 5 : "+findElementRotatedSortedArray(arr,0,arr.length-1,5));
    }
    public  static  int findElementRotatedSortedArray(int[] arr,int low,int high,int number)
    {
        int mid;
        while(low<=high)
        {
            mid=low + ((high - low) / 2);;

            if(arr[mid]==number)
            {
                return mid;
            }
            if(arr[mid]<=arr[high])
            {
                // Right part is sorted
                if(number > arr[mid] && number <=arr[high])
                {
                    low=mid+1;
                }
                else
                {
                    high=mid-1;
                }
            }
            else
            {
                // Left part is sorted
                if(arr[low]<=number && number < arr[mid])
                {
                    high=mid-1;
                }
                else
                {
                    low=mid+1;
                }
            }
        }
        return -1;
    }
}

当你运行上面的程序时，你会得到以下输出：

Index of element 5 : 5