4
\$\begingroup\$

Given a sorted array consisting 0’s and 1’s. The task is to find the index of first ‘1’ in the given array. I submitted the below code in geeks for geeks and the execution time is 5.77. Need help in optimizing the below code.

class FindIndex {
    public static void main (String[] args) {
        Scanner scanner = new Scanner(System.in);
        int noOfTestCase = scanner.nextInt();

        while (noOfTestCase-- > 0) {
            int n = scanner.nextInt();
            int[] array = new int[n];
            int index = -1;
            for (int i = 0 ; i < n ; i++) {
                array[i] = scanner.nextInt();
                if (array[i] == 1 && index == -1) {
                    index = i;
                }
            }
            System.out.println(index);
        }
    }
}

Source

\$\endgroup\$
  • 1
    \$\begingroup\$ Right now you're walking down the entire array one element at a time. You know the array is sorted, you know where it begins, where it ends, and where the middle is. Can you think of a way to keep track of those three pointers (low, mid, high) and work them towards each other until they meet? \$\endgroup\$ – Coupcoup Sep 13 at 5:33
  • \$\begingroup\$ but anyway you have to traverse n times to get the input right? \$\endgroup\$ – learner Sep 13 at 6:13
  • 2
    \$\begingroup\$ For the outer While loop? Yeah, you read every element of that once. For the inner loop no. This type of problem is called a binary search (the most basic example of which is guessing a number and getting high/low as a response) but a slightly more complicated variation where instead of one guess you're sliding three guesses back and forth until they meet. The solution will be O(log(n)) complexity. If you don't know what that means Google Big-O complexity. Walking a list is O(n). Walking a nested lists is O(n^2). etc \$\endgroup\$ – Coupcoup Sep 13 at 6:23
  • \$\begingroup\$ Got your point. Thanks :) \$\endgroup\$ – learner Sep 13 at 7:53
  • \$\begingroup\$ @Coupcoup Hmm, why would you suggest binary searching an array in a problem where they clearly shouldn't store the array in the first place? \$\endgroup\$ – superb rain Sep 13 at 12:20
1
\$\begingroup\$

Trying to outsmart the challenge defeats the purpose

While there is value in learning how to do the bare minimum needed (as you try to detect the number as soon as it is inputted instead of performing a search), there is only so much you can learn by trying to outsmart the challenge and not practice the knowledge this challenge is supposed to help you practice (which in this case is binary search).

Input reading

You can read the input faster using BufferedReader, see this answer's "Reading Data" section for example. You can read a whole line at once and then perform a search.

Binary search

Binary search is a very fast way to find an item in a sorted array where by looking at any element you know if what you're looking for is on the left or right of the current position.

You can perform the search on the string, converting the string to an array of numbers is unnecessary and therefore a waste of time.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.