CODEWITHSUNDEEP
javabinary-search
Alexander Pinzon Fernandez
Alexander Pinzon Fernandez

Reputation: 51

Interview topic: Binary search for a range

I feel a little frustrated because they did not hire me for not achieving the goal, but I think it is not possible.

The Problem: "Given an array with sorted data, e.g. 0, 1, 2, 4, 4, 6, 7, 7, 7, 7, 8, 9, 10, 12, 15, 15 Write a java class that implements binary search in O(log(n)) to find all instances of element X (for instance X=7), and the accompanying JUnit unit tests. Return all the indices if the element is found at least once, or -1 if not found. Explicitly identify any assumption you are making while solving this problem."

I find the way to get the left index and right index of the element in log(n) time.

But how can you return ALL THE INDICES in log(n) time, any idea?

Upvotes: 1

Views: 879

Answers (3)

Nir Alfasi
Nir Alfasi

Reputation: 53535

I'm not going to implement binarySearch for you because you can find many code examples online that do just that. Instead, I'll demonstrate what you can do once you've found one of the indices of the number you're looking for:

The algorithm is pretty simple, you iterate backwards until you reach the first occurrence of the number, and then iterate forward and add all the indices into a result list.

public static void main(String[] args) {
    int[] arr = {0, 1, 2, 4, 4, 6, 7, 7, 7, 7, 8, 9, 10, 12, 15, 15 };
    List<Integer> indices = findIndices(arr, 7);
    System.out.println(indices);
}

static List<Integer> findIndices(int[] arr, int num) {
    // here we may have one of the indices of 7: [6, 7, 8, 9]
    int index = Arrays.binarySearch(arr, num);
    List<Integer> result = new LinkedList<>();

    if (index < 0) { // not found
        result.add(-1);
    } else {  // found, now go backwards till the first one
        while (index > 0 && arr[index-1] == num) {
            index--;
        }
        // add all indices to the result-list
        while (arr[index] == num) {
            result.add(index++);
        }
    }
    return result;
}

Upvotes: 1

tiborK
tiborK

Reputation: 383

Finding the index of an element using binary search would take log(n) time. Since the array is sorted you can print out the element next to that index. That should take log(n)+k, where k is the number of occurences and that should be still log(n) depending of course how many times the searched element occurs.

Upvotes: 0

TextGeek
TextGeek

Reputation: 1247

In the worst case, such as if the list were all "7"s, @Duarte Meneses' method of walking outward to find both ends would take O(n), not O(log n).

If you find both ends by binary search (as OP says they did), and just return the indexes to both ends, that would be O(log n).

But if the questioner precisely intended to exclude that when they asked you to "return all the indexes", then in the worst case you can't do it, because there are more than log n items to return, and merely making the list to return would take longer than O(log n) -- even if you magically found them all in 0 time.

Upvotes: 1

Related Questions