C++程序在排序和旋转的数组中搜索元素

通过二分查找，可以在O(log n)时间内找到排序数组中的元素。但是假设我们在某个未知的枢轴上旋转了一个升序排序的数组。例如，1 2 3 4 5可能变成3 4 5 1 2。设计一种在旋转数组中找到元素的方法，并在O(log n)时间内完成。

C++程序在排序和旋转的数组中搜索元素

例子：

输入: arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 3
输出: 在索引8处找到

输入: arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 30
输出: 没有找到

输入: arr[] = {30, 40, 50, 10, 20}
key = 10

输出: 在索引3处找到

所有提供的解决方案都假定数组中的所有元素都是不同的。

基本解决方案：

方法：

想法是找到枢轴点，将数组分成两个子数组并进行二分搜索。
找到枢轴的主要思想是 – 对于排序后（按递增顺序）和枢轴变化的数组，枢轴元素是唯一的元素，其中下一个元素比它小。
可以使用上述语句和二分搜索找到枢轴。
找到枢轴之后，将数组分成两个子数组。
现在，单个子数组已排序，因此可以使用二分搜索来查找元素。

实现：

输入 arr[] = {3, 4, 5, 1, 2}
要搜索的元素 = 1
1) 找到枢轴点并将数组分成两个子数组。(枢轴=2)/索引为5/
2) 现在为两个子数组之一调用二分搜索。
(a) 如果元素大于0th元素，则在左侧数组中搜索
(b) 否则在右侧数组中搜索
(1将进入else，因为1小于0th元素(3))
3) 如果在所选子数组中找到元素，则返回索引
否则返回-1。

下面是上述方法的实现：

/* C++程序：在已排序并旋转的数组中搜索元素*/
#include <bits/stdc++.h>
using namespace std;
  
/* 标准的二分查找函数*/
int binarySearch(int arr[], int low,
                 int high, int key)
{
    if (high < low)
        return -1;
  
    int mid = (low + high) / 2; /*low + (high - low)/2;*/
    if (key == arr[mid])
        return mid;
  
    if (key > arr[mid])
        return binarySearch(arr, (mid + 1), high, key);
  
    // else
    return binarySearch(arr, low, (mid - 1), key);
}
  
/* 函数用于获取枢轴。对于数组3, 4, 5, 6, 1, 2，
    它返回3（即6的索引）*/
int findPivot(int arr[], int low, int high)
{
    // 边界情况
    if (high < low)
        return -1;
    if (high == low)
        return low;
  
    int mid = (low + high) / 2; /*low + (high - low)/2;*/
    if (mid < high && arr[mid] > arr[mid + 1])
        return mid;
  
    if (mid > low && arr[mid] < arr[mid - 1])
        return (mid - 1);
  
    if (arr[low] >= arr[mid])
        return findPivot(arr, low, mid - 1);
  
    return findPivot(arr, mid + 1, high);
}
  
/* 在大小为n的旋转排好序的arr []中搜索元素键*/
int pivotedBinarySearch(int arr[], int n, int key)
{
    int pivot = findPivot(arr, 0, n - 1);
  
    // 如果我们没有找到枢轴，
    // 那么整个数组都没有旋转
    if (pivot == -1)
        return binarySearch(arr, 0, n - 1, key);
  
    // 如果我们找到了枢轴，那么先和枢轴进行比较，
    // 然后在枢轴周围的两个子数组中搜索
    if (arr[pivot] == key)
        return pivot;
  
    if (arr[0] <= key)
        return binarySearch(arr, 0, pivot - 1, key);
  
    return binarySearch(arr, pivot + 1, n - 1, key);
}
  
/* 驱动程序以检查上述函数*/
int main()
{
    // 让我们在下面的数组中搜索3
    int arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int key = 3;
  
    // 函数调用
    cout << "该元素的索引是："
         << pivotedBinarySearch(arr1, n, key);
  
    return 0;
}

输出:

该元素的索引是：8

复杂度分析:

时间复杂度: O(log n)。二分查找需要log n次比较才能找到元素。因此时间复杂度是O(log n)。
空间复杂度: O(1)，不需要额外的空间。

改进的方案:

方法: 与其进行两次或更多次二分搜索，不如在一次二分搜索中找到结果。需要修改二分搜索来执行搜索。想法是创建一个递归函数，该函数将l和r作为输入范围，并且key作为输入。

1) 找到中间点mid=(l+h)/2
2) 如果关键字存在于中间点，则返回中间点
3) 否则 , 如果arr[l..mid]已排序
a) 如果要搜索的关键字位于arr[l]
到arr[mid]的范围内，请对arr[l..mid]进行递归。
b) 否则，请对arr[mid+1..h]进行递归。
4) 否则 (arr[mid+1..h]必须排序)
a) 如果要搜索的关键字位于arr[mid+1]
到arr[h]的范围内，请对 arr[mid+1..h]进行递归。
b) 否则，请对arr[l..mid]进行递归。

下面是上述思路的实现:

// 使用单次二分查找在已排序且旋转的数组中搜索元素
#include<bits/stdc++.h>
using namespace std;

// 如果arr[l..h]中存在键，则返回键的索引，否则返回-1
int search(int arr[], int l, int h, int key)
{
  if (l> h)
    return -1;

  int mid = (l + h) / 2;
  if (arr[mid] == key)
    return mid;

  // 如果arr[l...mid]是有序的
  if (arr[l] <= arr[mid]) {
    // 由于此子数组是已排序的，因此我们可以快速检查键位于哪一半或另一半
    if (key >= arr[l] && key <= arr[mid])
      return search(arr, l, mid - 1, key);
    // 如果键不在第一半子数组中，则将另一半分为两个子数组，
    // 以便我们可以快速检查键位于另一半中
    return search(arr, mid + 1, h, key);
  }

  // 如果arr[l..mid]的第一个子数组未排序，则arr[mid... h]必须是已排序的子数组
  if (key >= arr[mid] && key <= arr[h])
    return search(arr, mid + 1, h, key);

  return search(arr, l, mid - 1, key);
}
 
// 主程序
int main()
{
  int arr[] = {4,5,6,7,8,9,1,2,3};
  int n = sizeof(arr)/sizeof(arr[0]);
  int key = 6;
  int i = search(arr, 0, n-1, key);

  if (i != -1)
    cout << "Index: " << i << endl;
  else
    cout << "Key not found";
}