给定一个以升序排序并在某个枢轴旋转的数组，给定要搜索的目标值，如果在数组中找到则返回其索引

问题说明：

Initial Sorted array:
[0,1,2,4,5,6,7]
After rotation it becomes [4,5,6,7,0,1,2].
Target = 0
Index = 4 [as array index starts from 0]

该问题可以通过两种方式解决：

1. 线性搜寻
2. 修改后的二进制搜索

1. 线性搜索：

在此解决方案中，我们一一搜索元素并返回索引。但是，来吧，我们将给面试官2^nd 解。

2. 修改后的二进制搜索

我们可以通过使用修改后的二进制搜索来解决此问题。

在二进制搜索中，我们将排序后的数组分为2部分。并根据中间元素更改较低的索引和较高的索引。

由于数组未排序，因此无法在此处应用相同的解决方案。但是我们知道在一个分割的数组中总是有一半被排序。因此，我们需要找到数字是在排序部分中还是在旋转部分中。

我们使用以下代码实现相同的目的：

int binary_search_modified(vector<int>& array, int target) 
{
    int low = 0;
    int high = array.size()-1;

    while (low <= high) 
    {
        int mid = ( high-low )/2 + low;
        if (array[mid] == target)
            return mid;

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

让我们以一个例子来理解

Input: 
4, 5, 6, 7, 0, 1, 2

Target = 0

Pass 1:
    low = 0
    high = 6

    while(0 <= 6) true
        mid = (6-0) / 2 + 0
            = 3
        if array[3] == target ? false

        if(array[3] < array[6]) => (7 < 2) ? false
            else case
                if(array[0] <= target && target < array[3]) => (4 <= 0 && 0< 7) false
                    else case
                        low = mid + 1 => 3 + 1 >4

Pass 2:
    low = 4
    high = 6
    while (4 <= 6) true
        mid = (6 - 4)/2 + 4 = 5

    if(array[5] == target) ? false

    if(array[5] < array [6]) => (1 < 2 ) true
        if(array[5] < target) && (target <= array[6]) => (1<0 && 0<=2) false
            high = mid -1 => 5 - 1 = 4

Pass 3:
    low = 4
    high = 4

    while(4 <= 4)
        mid = (high - low)/ 2 +low => 4

    if array[4] == target => true
        return 4	

C ++解决方案

/*
* File     : search_in_sorted_array.cpp
* Purpose  : Search the target element in a sored array, but reversed at an index
*/
#include<iostream>
#include<vector>
using namespace std;

int binary_search_modified(vector<int>& array, int target) 
{
    int low = 0;
    int high = array.size()-1;

    while (low <= high) 
    {
        int mid = ( high-low )/2 + low;
        if (array[mid] == target)
            return mid;

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

int main()
{

    vector<int> array;

    array.push_back(4);
    array.push_back(5);
    array.push_back(6);
    array.push_back(7);
    array.push_back(0);
    array.push_back(1);
    array.push_back(2);

    int target = 0;


    for (int i = 0; i < array.size(); i++)
    {
        cout <<array[i] << " ";
    }
    cout<<endl;


    int index = binary_search_modified (array, target);
    
    if (index)
    {
        cout<<"The target = "<<target <<" found at index = "<< index<<endl;
    }
    else
    {
        cout<<"Target not found"<<endl;
    }

}

输出：

4 5 6 7 0 1 2
The target = 0 found at index = 4

该网站上可用的教程列表：