How to find the first occurrence using binary search in Java

Introduction

A binary search is an algorithm that searches for an element in a sorted array.

Refer to the following shots to learn more about Binary Search:

In this shot, we will modify the binary search algorithm to return the first occurrence of an integer in an array of integers sorted in ascending order.

Algorithm

In binary search, once we encounter the search target, we stop searching and return the middle index as the index of the search target. If the search ends with an empty half (left > right), then we terminate the search, returning “element is not found.”

In order to get the first occurrence, even after encountering the search target, we keep continuing the search for the target element on the left half until we reduce our search space to a single element (left = right).

The search is terminated in the following situations:

  1. If the target element is not present.
  2. Your current search space is reduced to a single element with the first occurrence of the search target.

Implementation using Java

Below is the Java code to implement the logic described above. You may run this to see it return the first occurrence of the search target for various test cases:

public class Main {
  public static int getFirstOccurence(int[] array, int target){  
    
    // Return not found if array is emtpy 
    if (array == null || array.length == 0)
      return -1; 
    // Intializing left and right positions 
    // of the search space
    int left = 0;
    int right = array.length - 1;
    // Searches until you have atleast two elements
    // in your search space
    while(left < right) {
        // Prevents integer overflow
        int mid = left + (right - left)/2;
        
        // if middle element is equal to search target,
        if(array[mid] == target) {
            // discard search space to the right of mid.
            right = mid;              
        } else {
            // discard search space from left to mid
            left = mid + 1;
        }
    }
    
    // after while loop, left will be equal to right
    // i.e. you have only one element in search space
    // return not found if its no equal to search target
    // else return its index as first index.   
    return (array[left] == target) ? left : -1;
  }
  
  public static void main(String[] args) {
    // empty array
    int[] test = {}; 
    
    // array with odd length
    int[] test0 = {0, 0, 1, 1, 2, 3}; 
    
    // array with single element containing search target
    int[] test1 = {1};     
    
    // array with single element not containing search target
    int[] test2 = {0}; 
    
    // array with even length
    int[] test3 = {0, 0, 2, 2, 2, 3}; 
     // array containing search target at the end
    int[] test4 = {0, 0, 0, 0, 3};
    
    // array not containing search target
    int[] test5 = {0, 1, 1, 2, 2};
    System.out.println(getFirstOccurence(test, 1));
    System.out.println(getFirstOccurence(test0, 1));
    System.out.println(getFirstOccurence(test1, 1));
    System.out.println(getFirstOccurence(test2, 2));
    System.out.println(getFirstOccurence(test3, 2));
    System.out.println(getFirstOccurence(test4, 3));
    System.out.println(getFirstOccurence(test5, 3));
  }
}

Next Steps

To further strengthen your understanding, try implementing the code to return the last occurrence of the target element using a similar approach.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)