Binary search in unsorted array

Question

I came across this problem: Given unsorted array, find how many elements can be found using binary search - ex : [5,4,6,2,8] -> Ans : 3 -> '6' and '8' and '5' can be found using binary search

I can't even understand what it means to do a binary search on unsorted array. Can someone please explain the problem?

There's also a code that solves this problem:

private static int countPossibleMatches(int[] array, int left, int right, int min, int max) {
        if (right < left) {
            return 0;
        } else if (right == left) {
            return (array[left] >= min && array[left] <= max? 1 : 0);
        } else {
            int middle = (left + right) / 2;
            int count = (array[middle] >= min && array[middle] <= max ? 1 : 0);
            count += countPossibleMatches(array, left, middle - 1, min, Math.min(array[middle], max));
            count += countPossibleMatches(array, middle + 1, right, Math.max(array[middle], min), max);
            return count;
        }
    }

    static int countPossibleMatches(int[] array) {
        return countPossibleMatches(array, 0, array.length - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

Eran · Accepted Answer · 2019-06-24 11:49:47Z

3

Binary search doesn't work for unsorted arrays. That said, if you ignore the fact that the array is unsorted and you run binary search algorithm on it, for some inputs it might succeed in finding the index of the element you are looking for.

For example, the first step of the binary search algorithm requires you to check the element are the middle index of the array. Therefore, if you are searching for the element that happens to be in that position, your binary search will find it, regardless of whether or not the array is sorted.

Therefore

find how many elements can be found using binary search

asks you to answer for a given array, how many of its elements can be found via binary search algorithm.

answered Jun 24, 2019 at 11:49

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

adamson Over a year ago

So to make sure. Running binary search On the array: 5, 4, 6, 2, 8 and target = 5, 6 or 8 will return true?

Eran Over a year ago

@adamson well, not "true", binary search returns the index of the element you are looking for (not a boolean). But, yes, for the inputs 5,6 and 8, binary search on that array will return the correct index of the number you are looking for.

Popovkov57 · Accepted Answer · 2022-07-23 17:48:39Z

A binary search splits the array into two equal pieces and determines which half the target it is. It repeats this process until only one element is left.

If the array is unsorted, the algorithm doesn't work correctly.

Exemple

import java.util.Arrays;

public class ClassB {

    public static void main(String[] args) {
        
        int[] numbersSorted = {2, 4, 6, 8};
        int[] numbersUnsorted = {4, 8, 6, 2};

        System.out.println(Arrays.binarySearch(numbersSorted, 2)); // 0
        System.out.println(Arrays.binarySearch(numbersSorted, 4)); // 1
        System.out.println(Arrays.binarySearch(numbersSorted, 1)); // -1
        System.out.println(Arrays.binarySearch(numbersSorted, 3)); // -2
        System.out.println(Arrays.binarySearch(numbersSorted, 9)); // -5

        System.out.println(Arrays.binarySearch(numbersUnsorted, 2)); // -1
        System.out.println(Arrays.binarySearch(numbersUnsorted, 4)); // 0
        System.out.println(Arrays.binarySearch(numbersUnsorted, 1)); // -1
        System.out.println(Arrays.binarySearch(numbersUnsorted, 3)); // -1
        System.out.println(Arrays.binarySearch(numbersUnsorted, 9)); // -5

    }

}

Collectives™ on Stack Overflow

Binary search in unsorted array

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related