Help with exercise

[jovulena]

Hello,
I am working on some exercises in c++,and i am stuck on this one. Could someone help me? Thenk you

The aim of this exercise is to check the presence of a number in an array.

Specifications:
The items are integers arranged in ascending order.
The array can contain up to 1 million items
The array is never NULL
Implement the method bool Answer::exists(int ints[], int size, int k) so that it returns true if k belongs to ints, otherwise the method should return false. size contains the size of ints.

Important note: Try to save CPU cycles if possible.

Example:
int ints[] = {-9, 14, 37, 102};
Answer::exists(ints, 4, 102) returns true
Answer::exists(ints, 4, 36) returns false

[Ganado]

What have you tried so far?

[jovulena]

So far I have this.

#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;
            } else return false;
        }
    }
};

[Ganado]

Okay, great. First let's focus on getting it correct.
Your for loop in your function returns every time during the first iteration.
In other words, i will never be 1 or more.

Do you see why? Both branches of your if-statement return something.

Once you fix that, the "note" your instructor gives sounds more like a command. While it's actually not true that binary search will always be faster than a linear search (due to CPU caching/branch prediction), I believe your instructor wants you to use a binary search algorithm because you know the data is sorted.

PS: Your unistd.h and sys/ headers are *nix-specific and not portable C++. They also aren't needed for what you're doing. In fact, none of those headers are needed for the code you have shown (but I assume you at least use <iostream> somewhere to use cout).

[jlb]

Okay with your code, you check the first ints, if it is not equal to k you return false instead of testing the next number, why?


Also this brute force method will probably take too long, perhaps you should use the fact that the array is sorted. There are much faster methods to search a sorted array.

[Manga]

#include <iostream>

using namespace std;

bool exists(int[], int, int);

int main () {
    
   int ints[] = {-9, 14, 37, 102};
   
   cout << exists(ints, 4, 102) << endl;
   cout << exists(ints, 4, 36) << endl;
    
 return 0;   
}

bool exists(int array[], int size, int value) {
 for(int i = 0; i < size; i++) {
  if(array[i] == value) {
   return true;   
  }
 }
    return false; 
}

A method does not require a full class unless that is one of the requirements...