使用递归二进制搜索

Question

我目前正在编写程序，其中在一项任务中，我必须使用二进制递归函数来搜索数组中的整数并显示目标的索引。

但是，由于此特定功能输出的索引与正确的索引不同，因此我遇到了麻烦。

如果有人可以帮助解决此错误，我将不胜感激！

我当前的代码

#include <iostream>
using namespace std;

int linearSearch(int [], int, int, int);
int binarySearch(int [], int, int, int);

void reverseArray(int arr[], int index1, int index2)
{
    if(index2 > index1)
    {
        swap(arr[index2], arr[index1]);
        reverseArray(arr, index1 + 1, index2 - 1);
    }
}

void printArray(int arr[], int SIZE)
{
    for(int i = 0; i < SIZE; i++)
    cout << arr[i] << " ";
    cout << endl;
}

int getSum_Linear(int arr[], int SIZE)
{
    if(SIZE <= 0)
        return 0;

    return(getSum_Linear(arr, SIZE - 1) + arr[SIZE - 1]);
}

int getSum_Binary(int arr[], int SIZE)
{
    if(SIZE == 1)
        return arr[0];
    else
    {
        int mid = SIZE / 2;
        return(getSum_Binary(arr, mid) + getSum_Binary(arr + mid, SIZE - mid));
    }
}

int main()
{
    const int SIZE = 9;
    int arrInt[SIZE] = {11, 22, 33, 44, 55, 66, 77, 88, 99};

    /// Enter your testing code for Task 1, 2 and 3 here

    cout << "// Task 1" << endl << endl;

    // Print original array.
    cout << "Original array: " << endl;
    printArray(arrInt, SIZE);

    // Reverse array.
    cout << endl;
    reverseArray(arrInt, 0, SIZE - 1);

    // Print reversed array.
    cout << "Reversed array: " << endl;
    printArray(arrInt, SIZE);

    cout << endl << "// Task 2" << endl << endl;

    cout << "Linear sum of array: " << getSum_Linear(arrInt, SIZE) << endl;

    cout << endl << "// Task 3" << endl << endl;

    cout << "Binary sum of array: " << getSum_Binary(arrInt, SIZE) << endl;

    cout << endl << "// Task 4" << endl << endl;

    int target = 99;
    int pos = linearSearch(arrInt, 0, SIZE, target);

    cout << "Linear search: The position of the target " << target << " is " << pos << endl;

    target = 66;
    pos = linearSearch(arrInt, 0, SIZE, target);
    cout << "Linear search: The position of the target " << target << " is " << pos << endl;

    cout << endl << "// Task 5" << endl << endl;

    target = 99;
    pos = binarySearch(arrInt, 0, SIZE - 1, target);
    cout << "Binary search: The position of the target " << target << " is " << pos << endl;

    target = 66;
    pos = binarySearch(arrInt, 0, SIZE - 1, target);
    cout << "Binary search: The position of the target " << target << " is " << pos << endl;

    return 0;
}

int linearSearch(int arrInt[], int pos, int SIZE, int target)
{
    if(pos >= SIZE)
    {
        return -1;
    }
    else if(arrInt[pos] == target)
    {
        return pos;
    }
    else
    {
        return linearSearch(arrInt, pos + 1, SIZE, target);
    }
}

int binarySearch(int arrInt[], int begIndex, int endIndex, int target)
{
    if (endIndex >= begIndex)
    {
        int midIndex = begIndex + (endIndex - begIndex) / 2;

        if (arrInt[midIndex] == target)
            return midIndex;

        if (arrInt[midIndex] > target)
            return binarySearch(arrInt, begIndex, midIndex - 1, target);

        return binarySearch(arrInt, midIndex + 1, endIndex, target);
    }

    return -1;
}

我的当前输出

// Task 1

Original array:
11 22 33 44 55 66 77 88 99

Reversed array:
99 88 77 66 55 44 33 22 11

// Task 2

Linear sum of array: 495

// Task 3

Binary sum of array: 495

// Task 4

Linear search: The position of the target 99 is 0
Linear search: The position of the target 66 is 3

// Task 5

Binary search: The position of the target 99 is -1
Binary search: The position of the target 66 is -1

Answer 1

问题是您正在使用递归二进制搜索功能，该功能旨在处理以升序而不是降序排列的列表。问题出在这行代码：

 if (arrInt[midIndex] > target)
            return binarySearch(arrInt, begIndex, midIndex - 1, target);

对于以降序排列的整数数组，需要颠倒比较。例如，此变体：

int reversedBinSearch(int arr[], int begDex, int endDex, int target) {
    if (endDex < begDex) {  //failure case terminates recursion
        return -1;
    }
    else {
        int midDex = begDex + (endDex - begDex) / 2;
        if (arr[midDex] == target) {
            return midDex;
        }
        else if (arr[midDex] < target) {
            return binSearch(arr, begDex, midDex - 1, target);
        }
        else {
            return binSearch(arr, midDex + 1, endDex, target);
        }
    }
}

没有进行更改，您最终将搜索错误的块。