在本教程中，我们将看到如何在排序和旋转数组中搜索元素。

问题：

我们提供了如下排序和旋转的阵列：

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

如果我们注意到阵列被排序和旋转。
我们需要在O(log n)时间复杂度中搜索上面的数组中的一个元素。

解决方案：

我们可以使用线性搜索在上面的数组中搜索一个元素，但这将需要o(n)。
我们可以使用二进制搜索算法的变体来解决上述问题。
我们可以使用我们可以将数组分成两个排序的子阵列({3,5,8,10})，尽管我们不需要查找枢轴点(元素开始减少)。

算法：

• 计算中期：低+高/2.
• 检查[中间...高]是排序的
• 如果数字位于范围之间，则低= MID + 1.
• 如果数字不在范围内，高=中间1.
• 检查是否对[LOW..MID]进行了排序。
• 如果数字位于范围之间，高= 1.
• 如果数字不在范围内，则低= MID + 1.

让我们通过示例来理解这一点。

在上面的阵列中搜索5所涉及的步骤：

• 计算中期：3(0 + 7/2)
• mid> a high&& 5 <a low&& 5 <a high，所以数字(5)位于右侧部分，所以较低中期+ 1.
• a [mid] == 5，所以你可以返回它。

Java程序以在排序和旋转数组中搜索一个元素：

创建一个名为的类

searchelementsortedandrotatedarraymain.java。

package org.igi.theitroad;
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