Find an element in a list/array (a big list)

Question

I'm actually doing an easy CodinGame --> I have to find if an element exists in a list.

I've tested a first solution, it was working but it wasn't really optimized (according to the machine).

So I've tried another solution but : When I test my code for this 2nd solution, it returns the right answers but when I'm submitting my code, it tells me that my solution is completely wrong (it doesn't work if the list is empty, and also if the list is huge, ...).

Please can you help me ?

Here is my first naive solution :

public static boolean check(int[] ints, int k) {
        boolean res = false;
    
        for(int i : ints){
            if(i == k){
                res = true;
                break;
            }
        }
        return res;
    }

Here is the code of my 2nd solution that is supposed to be optimized:

static boolean exists(int [] ints, int k){
        boolean res = false;
        int first = 0;
        int last = ints.length;
        int mid = (first + last)/2;
        while(first <= last){
            if( ints[mid] < k){
                first = mid +1;
            }else if (ints[mid] == k){
                res = true; 
                break;
            }else{
                last = mid -1;
            }
         mid = (first + last)/2;
         }
         if(first > last){
            res = false;
         }
         return res;
     }

Are we to assume that the list is in some sort of order (biggest to smallest or smallest to biggest)? The reason why I am asking is because if the list is not in any order, then the quickest way to find an element would be to simply search for it from the start to the end of the array. — Novaordo, Dec 03 '22 at 15:20
`Arrays.asList(ints).contains(k)` should do the trick, but I suppose you're not allowed to use built-in functions like that? — JustAnotherDeveloper, Dec 03 '22 at 15:27
- The items are integers arranged in ascending order - The array can contain up to 1 million items - The array is never null - My method should do this : Exemple : int[] ints = {-9, 14, 37, 102}; exists(ints, 102) //returns true exists(ints, 36) //returns false — Unknown kind Panda, Dec 03 '22 at 18:02
Thank you for your answers, do you mean something like this ? : static boolean exists(int[] ints, int k){return Arrays.asList(ints).contains(k); } — Unknown kind Panda, Dec 03 '22 at 18:40

score 2 · Accepted Answer · answered Dec 12 '22 at 12:46

Finally I've found the solution to my problem !!!!!

Here it is :

import java.util.Arrays;

class A{
    static boolean exists(int[] ints, int k){
         boolean res = false;
         int index = Arrays.binarySearch(ints, k);
         if (index<0){
             res = false;
         }else{
             res = true;
         }
         return res;
      }
}

Albina · Answer 2 · 2022-12-04T15:31:22.430

0

I suppose you are trying to implement Binary search in the second solution.

If so, please check this answer. Your input array must be sorted in non-decreasing order, because Binary Search works only with sorted input data. For example, you can simply type Arrays.sort(arr); and then pass your array into exists() method. But the overall time&space complexities will be O(n log n).

Fixed some bugs in your implementation:

public static boolean exists(int[] ints, int k) {
    int first = 0;
    int last = ints.length - 1;
    while (first <= last) {
        int mid = first + (last - first) / 2; // to avoid integer overflow in extremely large arrays
        if (ints[mid] < k) {
            first = mid + 1;
        } else if (ints[mid] == k) {
            return true;
        } else {
            last = mid - 1;
        }
    }
    return false;
}

edited Dec 04 '22 at 15:31

answered Dec 03 '22 at 15:26

Albina

1,901
3
7
19

- The items are integers arranged in ascending order - The array can contain up to 1 million items - The array is never null - My method should do this : Exemple : int[] ints = {-9, 14, 37, 102}; exists(ints, 102) //returns true; exists(ints, 36) //returns false – Unknown kind Panda Dec 03 '22 at 18:18
Yes I'm trying to implement Binary search in my second solution. I've tried to used exists() method but k is an int and it returns an error : int cannot be dereferenced – Unknown kind Panda Dec 03 '22 at 18:56
@UnknownkindPanda added BS implementation, you can have a look. – Albina Dec 04 '22 at 11:03
Hi, I've tried the solution of @albina : It was only working when I remove the '-1' for example for : int[] ints = {-9, 14, 37, 102}; System.out.println(exists(ints, 102)); //true System.out.println(exists(ints, 36)); //false – Unknown kind Panda Dec 04 '22 at 14:10
But when I say "working" I mean that when I test the code the solution has a good behavior with true and false, but when I submit it on the codingame the machine tells me that is wrong. – Unknown kind Panda Dec 04 '22 at 14:11
@UnknownkindPanda please check now, I fixed a bug `while (first <= last)`. – Albina Dec 04 '22 at 14:18
I've tried your solution but it tells me now that I have to write return statement, I tried to put an image of the whole page of the exercise but I can't for the moment because I'm a beginner on Stack Overflow. I've also tried to create a boolean variable res, initialized to false and to put a return statement but it tells me that my solution is not optimized enough to handle some cases. – Unknown kind Panda Dec 04 '22 at 15:29

Find an element in a list/array (a big list)

Here is my first naive solution :

Here is the code of my 2nd solution that is supposed to be optimized:

2 Answers2