使用二进制搜索检查数组中是否存在数字

Question

我有一个测试评估需要做。有一个问题一直困扰着我。

我有一个数字数组，我需要找到一种方法来在数组中找到该数字，我已经部分完成了。问题出现在项目的下一步，即它必须容纳一百万个项目。

我相信这是二进制搜索。我如何进行二进制搜索或等效搜索？

#include <iostream>
#include <sys/resource.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h> 
#include <sys/types.h>
#include <algorithm>
#include <vector>

using namespace std;

class Answer
{
public:
    static bool exists(int ints[], int size, int k)
    {

        for(int i=0; i<size; i++){

            if(ints[i]<k){
                return true;


            }
        }
        return false;
    }
};

下面的图片说明了我需要什么和我的代码

我需要的：

Answer 1

为什么不直接使用标准库函数呢？

    static bool exists(int ints[], int size, int k)
    {
        return std::binary_search(ints, ints + size, k);
    }

Answer 2

我已经看到你得到了答案，但是自己实现二分查找总是好的，特别是在算法课程中，所以它可能会帮助你理解算法：

 static bool exists(const int ints[], int size, int k) {
    int left = 0, right = size-1;

    while(right-left>1) {
        int middle = (right+left)/2;

        if(ints[middle] > k) right = middle;
        else left = middle;
    }

    if(ints[right] == k || ints[left] == k) return true;
    return false;
}

使用二进制搜索检查数组中是否存在数字

Check the presence of a number in an array with binary search

c++

arrays

binary-search