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

I have a test assessment that I need to do. There is one question that I have been having trouble with.

I have an array of numbers and I need to find a way to find that number in the array, which I have partially done. The problem becomes in the next step of the project which is that it has to accommodate a million items.

I believe this is binary search. How do I do a binary search or equivalent?

#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;
    }
};

The images below gives an idea of what I need and my code

What I need:

CodePudding user response：

Why don't you just use standart lib function?

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

CodePudding user response：

I have already seen you got the answer, but it's never bad to implement binary search yourself, especially on the algorithm course, so may be it will help you to understand the algorithm:

 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;
}