判断下面的二分搜索算法是否正确。 int binarySearch(int a[], const int x, int n) { if(n>0 && x >= a[0]) { int left = 0; int right = n - 1; while(left < right) { int middle = (left + right + 1) / 2; if(x < a[middle]){ right = middle; } else{ left = middle; } } if(x == a[left]) { return left; } } return -1; }

这个二分搜索算法是错误的。

当x >= a[0]且n>0时，进入while循环后，如果x < a[middle]，则令right = middle，这是错误的，正确的应该是right = middle - 1，因为此时a[middle]已经被排除在候选区之外了，应该从中间的左边开始搜索下一个候选区。

另外，当left == right时，应该退出循环，而不是在循环内部再次比较一次。

改正后的代码如下：

int binarySearch(int a[], const int x, int n) {
    if(n > 0 && x >= a[0]) {
        int left = 0;
        int right = n - 1;
        while(left <= right) {
            int middle = (left + right) / 2;
            if(x < a[middle]) {
                right = middle - 1;
            } else if(x > a[middle]) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
    }
    return -1;
}

相关问题

用c++给出在一个递增有序表A中采用二分查找算法查找值为x的蒜素的递归算法

好的，针对您的问题，我可以给出以下的算法实现：

// 在有序表A中采用二分查找算法查找值为x的元素
// lo和hi分别表示当前查找范围的左右端点
// 如果找到，返回下标；否则返回-1
int binarySearch(const vector<int>& A, int x, int lo, int hi) {
    if (lo > hi) {  // 查找失败
        return -1;
    }
    int mid = lo + (hi - lo) / 2;
    if (A[mid] == x) {  // 找到x
        return mid;
    } else if (A[mid] < x) {  // x在右半部分
        return binarySearch(A, x, mid+1, hi);
    } else {  // x在左半部分
        return binarySearch(A, x, lo, mid-1);
    }
}

以上就是采用递归方式实现的二分查找算法，您可以根据实际情况进行调用。

请给出具体代码比较1亿个数据中各种查找算法的效率，包括顺序查找，二分查找，分块查找，hash查找

以下是代码实现，用于比较在1亿个数据中各种查找算法的效率：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

const int SIZE = 100000000; //一亿个数据
const int BLOCK_SIZE = 1000; //分块查找块的大小

vector<int> data; //存储1亿个数据

void init()
{
    data.reserve(SIZE);

    srand(time(NULL));
    for (int i = 0; i < SIZE; i++)
    {
        data.push_back(rand()); //随机生成数据
    }
}

//顺序查找
int sequentialSearch(int target)
{
    for (int i = 0; i < SIZE; i++)
    {
        if (data[i] == target)
            return i;
    }
    return -1;
}

//二分查找
int binarySearch(int target)
{
    int low = 0, high = SIZE - 1;

    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (data[mid] == target)
            return mid;
        else if (data[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }

    return -1;
}

//分块查找
int blockSearch(int target)
{
    vector<int> blockMax(BLOCK_SIZE, -1); //存储每个块的最大值
    for (int i = 0; i < SIZE; i += BLOCK_SIZE)
    {
        int blockIndex = i / BLOCK_SIZE;
        blockMax[blockIndex] = data[i + BLOCK_SIZE - 1];
    }

    //在块中进行二分查找
    int blockIndex = target / BLOCK_SIZE;
    int low = blockIndex * BLOCK_SIZE, high = min((blockIndex + 1) * BLOCK_SIZE - 1, SIZE - 1);

    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (data[mid] == target)
            return mid;
        else if (data[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }

    //如果目标值不在块中，则在块前进行二分查找
    for (int i = blockIndex - 1; i >= 0; i--)
    {
        if (blockMax[i] < target)
            return -1;
        int low = i * BLOCK_SIZE, high = min((i + 1) * BLOCK_SIZE - 1, SIZE - 1);
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (data[mid] == target)
                return mid;
            else if (data[mid] > target)
                high = mid - 1;
            else
                low = mid + 1;
        }
    }

    return -1;
}

//hash查找
int hashSearch(int target)
{
    vector<int> hashTable(SIZE);

    for (int i = 0; i < SIZE; i++)
    {
        hashTable[data[i] % SIZE] = i;
    }

    return hashTable[target % SIZE];
}

int main()
{
    init();

    //测试顺序查找
    clock_t start = clock();
    int index = sequentialSearch(data[SIZE - 1]);
    clock_t end = clock();
    if (index != -1)
        cout << "sequentialSearch: find target at index " << index << endl;
    cout << "Time cost: " << static_cast<double>(end - start) / CLOCKS_PER_SEC << endl;

    //测试二分查找
    sort(data.begin(), data.end()); //二分需要有序数组
    start = clock();
    index = binarySearch(data[SIZE - 1]);
    end = clock();
    if (index != -1)
        cout << "binarySearch: find target at index " << index << endl;
    cout << "Time cost: " << static_cast<double>(end - start) / CLOCKS_PER_SEC << endl;

    //测试分块查找
    start = clock();
    index = blockSearch(data[SIZE - 1]);
    end = clock();
    if (index != -1)
        cout << "blockSearch: find target at index " << index << endl;
    cout << "Time cost: " << static_cast<double>(end - start) / CLOCKS_PER_SEC << endl;

    //测试hash查找
    start = clock();
    index = hashSearch(data[SIZE - 1]);
    end = clock();
    if (index != -1)
        cout << "hashSearch: find target at index " << index << endl;
    cout << "Time cost: " << static_cast<double>(end - start) / CLOCKS_PER_SEC << endl;

    return 0;
}

运行以上代码，即可比较1亿个数据中各种查找算法的效率。其中，顺序查找的时间复杂度为O(n)，二分查找的时间复杂度为O(log n)，分块查找的时间复杂度为O(√n)，hash查找的时间复杂度为O(1)。在1亿个数据中，最好使用hash查找。