在三分之一处使用 "midpoint" 进行二分查找

Question

我想设计一种二进制搜索算法，使用递归将您要查找的项目与第 33 个百分位和第 66 个百分位的项目进行比较，而不是与中点进行比较。

这是我目前拥有的：

#include <iostream>
using namespace std;
//binary search recursion


int binarysearch(int begin, int end, int a[], int key);


void main()
{
    const int size= 10;

    int a[size] = { 22,32,45,55,65,75,90,100 };

    cout<<binarysearch(0, 7,a, 90);
}


int binarysearch(int begin,int end,int a[],int key)
{
    int b = begin+(end-begin) * (1.0/3.0);
    int c = begin +( end-begin)*(2.0 / 3.0);

    if (begin > end)
    {
        return -1;
    }
    if (a[b] == key)
    {
        cout << "b is the key";
        return b;
    }
    if (a[c] == key)
    {
        cout << "c is the key";
        return c;
    }

    if (a[begin] < key&&a[b]>key)
    {
        return binarysearch(begin, b-1, a, key);
    }

    if (a[b ] < key&&a[c ]>key)
    {
        return binarysearch(b + 1, c - 1, a, key);
    }

    if (a[c ] < key&&a[end]>key)
    {
        return binarysearch(c + 1, end, a, key);
    }

}

这样对吗？有什么建议吗？

Answer 1

您的递归逻辑仍然关闭。您不需要 begin2 和 end2 参数；它们只会增加混乱，没有任何用处。你的逻辑应该是这样的：

找到b和c，即1/3和2/3的区间。（你现在做对了）。
如果 a[b] 或 a[c] 等于 key，则您已找到结果。（你也做对了）。
否则判断key可能在三个区间中的哪一个。三种可能是[begin,b-1],[b+1,c-1]，以及 [c+1，end]。相应地递归。（这是你做的不对的部分。）

您还应该再添加一个逻辑：如果begin > end，那么密钥根本不在a中。

我不会说得比这更具体，因为这听起来像是一项任务，您应该编写自己的代码。

在三分之一处使用 "midpoint" 进行二分查找

Binary search with "midpoint" at one third

c++

algorithm

binary-search