CODEWITHSUNDEEP
java
adamson
adamson

Reputation: 43

Binary search in unsorted array

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

Upvotes: 4

Views: 1382

Answers (2)

Popovkov57
Popovkov57

Reputation: 303

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.

enter image description here

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

    }

}

Upvotes: 2

Eran
Eran

Reputation: 394146

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.

Upvotes: 3

Related Questions