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

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处找到

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

基本解决方案:

方法:

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

实现:

输入 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";
}  

输出:

Index: 2

复杂度分析:

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

如何处理重复项?

当允许有重复项时,似乎不可能在所有情况下以O(Logn)时间搜索。例如,在{2,2,2,2,2,2,2,2,0,2}和{2,0,2,2,2,2,2,2,2,2,2,2}中搜索0。

似乎不可能通过在中间做恒定数量的比较来决定是递归左半边还是右半边。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例