二进制搜索找到数字所在的范围 [英] Binary search to find the range in which the number lies

问题描述

我有一个数组

Values array: 12 20 32 40 52
              ^  ^  ^  ^  ^
              0  1  2  3  4

我必须执行二叉搜索找到索引数字所在的范围。例如：

on which I have to perform binary search to find the index of the range in which the number lies. For example:

1. 给定数字 - > 19（位于索引0和1之间），返回0


2. 给定数字 - > 22（它在索引1和2之间），返回1


3. 给定数字 - > 40（位于索引3和4之间） 3

我以下列方式实施二进制搜索，这对于情况1和3是正确的，搜索情况2或52，55 32等。

I implemented the binary search in the following manner, and this comes to be correct for case 1, and 3 but incorrect if we search for case 2 or 52, 55 32, etc.

#include <iostream>
using namespace std;

int findIndex(int values[], int number, unsigned first, unsigned last)
{
    unsigned midPoint;
    while(first<last)
    {
        unsigned midPoint = (first+last)/2;
        if (number <= values[midPoint])
            last = midPoint -1;
        else if (number > values[midPoint])
            first = midPoint + 1;
    }
    return midPoint;
}


int main()
{
    int a[] = {12, 20, 32, 40, 52};
    unsigned i = findIndex(a, 55, 0, 4);
    cout << i;
}

使用其他变量，例如 bool found 不允许。

Use of additional variables such as bool found is not allowed.

推荐答案

C或C ++中的范围通常指定为绑定，但一个超过上限。

A range in C or C++ is normally given as the pointing directly to the lower bound, but one past the upper bound. Unless you're feeling extremely masochistic, you probably want to stick to that convention in your search as well.

假设你要遵循这个约定，你的 last = midpoint-1; 不正确。相反，您要将最后一个设置为一个过去结束的范围，因此它应该是 last = midpoint;

Assuming you're going to follow that, your last = midpoint-1; is incorrect. Rather, you want to set last to one past the end of the range you're going to actually use, so it should be last = midpoint;

您还只需要进行一个比较，而不是两个。在二分搜索中，只要两个边界不相等，你就要设置中心点的下限或上限，所以你只需要做一个比较来决定。

You also only really need one comparison, not two. In a binary search as long as the two bounds aren't equal, you're going to set either the lower or the upper bound to the center point, so you only need to do one comparison to decide which.

至少按照惯例，在C ++中，使用< 而不是< =上面的任何一个都可以工作，但遵循仅使用< 的惯例，， code>不会对所包含的类型强加额外的（不必要的）要求。

At least by convention, in C++, you do all your comparisons using < instead of <=, >, etc. Any of the above can work, but following the convention of using only < keeps from imposing extra (unnecessary) requirements on contained types.

虽然大多数访问者可能不在乎， code> midpoint =（left + right）/ 2; 。我通常喜欢 midpoint = left +（right-left）/ 2;

Though most interviewers probably don't care, there's also a potential overflow when you do midpoint = (left + right)/2;. I'd generally prefer midpoint = left + (right - left)/2;

对于如何使用这个方式，我希望我可以相信你是诚实的：

Though I'm hesitant to post a direct solution to what's openly stated as an interview question, I'll hope I can trust you to be honest in how you use this:

template <class T>
T *lower_bound(T *left, T *right, T val) {
    while (left < right) {
        T *middle = left + (right - left) / 2;
        if (*middle < val)
            left = middle + 1;
        else
            right = middle;
    }
    return left;
}

template <class T>
T *upper_bound(T *left, T *right, T val) {
    while (left < right) {
        T *middle = left + (right - left) / 2;
        if (val < *middle)
            right = middle;
        else
            left = middle + 1;
    }
    return left;
}

这篇关于二进制搜索找到数字所在的范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！