First occurrence of element with binary search

First occurrence of element in sorted array

Given a sorted array and an element, find the first occurrence of key in array.  As array can contain duplicate values, there can be multiple occurrences of same element, problem is to find first index. For example, in given array, first occurrence of 4 is at index 3. Can you guess what is first occurrence of element 6?

first occurrence of element

Brute force solution would be to scan entire array and compare each A[index] with key. If A[index]  == key, then return index. Worst case time complexity of brute force method is O(N). Can we do better than it?

First occurrence of element : Thought process

One property of input array we did not use in brute force solution is array being sorted. To search in sorted array: binary search algorithm . If there are no duplicates in array, it will be super easy to find first instance using binary search, how can we modify it to solve problem with duplicates.
First question you should ask to yourself : What is candidate solution set? In plain terms, what can be a valid answer if there is key is present? Also, think about case when key is not present at all.

If key is present, candidate answer will be one of the indices. Range of indices is from 0 to array.length -1. We learned one concept  when solving for find greater or equal number or ceiling in sorted array. The concept was, we can apply binary search to any set of input where following condition is met :

Binary search can be used if and only if for all x in candidate Set Spredicate(x) implies predicate(y) for all y > x.

If A[index] is greater than or equal to key, than all A[y] will be greater than or equal to A[index] where y > index, which satisfies our condition.
This means when predicate return true, there is no point looking into right subarray, as all elements will be greater than or equal to key. First instance of key can not be more than index. Hence, discard Array[index+1, end] and look in left side of array, Array[start, index].
What should be start point for index? Obviously, it will be mid index. Based on if predicate(mid) is true or false, we discard right or left half of array.

When to stop? When just one element in array. at that point, check if that element is key, if yes return index else return -1.

First occurrence of element in sorted array : Example

Let’s take an example and see how it works? Take an array as shown below and find first instance of element 6.

Start with mid index and see if it is greater than or equal to key, it is not, so discard the left subarray including mid.

New array to be searched is from index 5 to 9. Find new mid, element at new mid is greater than or equal to key, in that case discard right subarray.

Search space is reduced from index 5 to 7. Mid is 6 and Array[6] is equal to key, so again discard right subarray.

first occurrence of element

Find mid again, which is 5. Array[5] is equal to key, so discard right sub array.

first occurrence of element

At this point, there is only one element left in candidate set. Is it equal to key? If yes, return the index.

first instance of element in sorted array Can you please draw the execution flow to find 1 and say 10 (which does not exist in array)? Does algorithm work for those cases?

First occurrence of element in sorted array : Implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {

    private static boolean isGreaterThanEqualTo(int[] a, int index, int key){
        if(a[index] >= key) return true;

        return false;
    }

    public static int findFirstOccurrence (int[] a, int start, int end, int key){

        while(start < end){
            int mid = start + (end - start) / 2;

            if(isGreaterThanEqualTo(a, mid, key)){
                end = mid;
            }
            else{
                start = mid + 1;
            }
        }
        return (a[start] == key) ? start : -1;
    }

    public static void main(String[] args) {
        int[] input = {3,10,11,15,17,17,17,20};

        int index = findFirstInstance(input,0, input.length-1, 20);
        System.out.print(index == -1 ? "Element not found" : "Element found at : " + index);
    }
}

Same method can be implemented recursively as follow

public static int findFirstOccurrence Recursive(int[] a, int start, int end, int key){

    while(start < end){
        int mid = start + (end - start) / 2;

        if(isGreaterThanEqualTo(a, mid, key)){
            return findFirstOccurrenceRecursive(a,start,mid, key);
        }
        else{
            return findFirstOccurrenceRecursive(a,mid+1,end, key);
        }
    }
    return (a[start] == key) ? start : -1;
}

Worst case complexity to find first occurrence of element in sorted array using binary search algorithm is O(log n).

What did we learn from this problem? First, how to identify if a problem can be solved using binary search. We learned how solution depends on candidate solution set. How can we discard some part of that set based on constraints in problem. For example, in this problem, candidate set was all indices of array, but based on constraint that element should be equal to key, half of those indices were discarded.
Remember to check last element for constraints of problem, if matches, then it is solution, else there is no solution.

Hope, this article helps you to prepare better for your interviews. If you find anything missing or wrong, please reach out to us through comments, email at communications@algorithmsandme.com