Java program to search an array using binary search algorithm

Posted on 09th March 2021

Consider an array of N integers and you need to find if a number, x, exist in that array. The easiest way of doing this is to take each element of the array from the first to the last and check if it matches the search value 100. This method is called a linear search and the problem with linear search is that it can be very time consuming, especially for larger arrays. The time complexity for linear search in the worst-case scenario is defined as O(n), where n is the number of elements in the array. The search can be done a lot quicker if the array is sorted. For example, consider a sorted array of six elements

[10, 15, 23, 40, 75, 80] 

The target value or the search values is, say 40.

In this case, you do not have to scan from the first element of the array, instead, you can do the following.

  1. Split the array down the middle to two halves. The position of the middle element is calcula

    middle postiion = (start index + end index) / 2
    middle postiion = (0 + 5) / 2 = 2 (ignore the decimal part)
    

    The middle position is 2 and middle element is 23. Therefore you will have two sub-arrays like below.

    First sub-array contains - [ 10, 15, 23]
    Second sub-array contains - [ 40, 75, 80]
    
  2. If the middle element is the target search element then search returns the element position.
  3. If the target element is less than the middle element then search the first half of the array.
  4. if the target element is greater than the middle element then search the second half of the array.
  5. Repeat steps 1 to 4 until you find the search element or the sub-array you are searching for contains more than one element.

    In case of our example array, the condition on step 4 holds true. So you have to repeat the steps 1 to 4 on the second sub-array

     [40, 75, 80]
    

This method of searching a target value in an array is known as a binary search. It's a type of "divide and conquer" algorithm where you continuously divide the problem into smaller parts and apply the same logic to get to the solution.

This algorithm can be used to find search for an element on both one dimensional and two dimensional arrays.

Binary Search on 2-D Arrays

Here is a Java program to search for a value in a two dimensional array using binary search algorithm.

public class Main {
   // Entry point
   public static void main(String[] args) {
		
      int[][] my_array = {{1, 6, 7},
                {8, 11, 13 },
                {18, 25, 31}};

      // Value to search
      int target = 25;
      
      // Call binarySearch method
      if (binarySearch(my_array, target) > 0)
         System.out.println("Found");
         
      else
         System.out.println("Not found");

}

  /**
  * Search a 2-D array for a target value.
  * @param a : 2-D array.
  * @param searchValue : Target value to search.
  * @return 1 if found and 0 if not found.
  */
public static int binarySearch(int a[][], int searchValue){
   int rows = a.length;
   int cols = a[0].length;
   int start = 0;
   int end = rows * cols - 1;
   int mid, midRow, midCol, midVal;

   while (start <= end) {
      mid = (start + end) / 2;
      midRow = mid / cols;
      midCol = mid % cols;
      midVal = a[midRow][midCol];
      
      if (midVal == searchValue){
         // Return 1 if target found
         return 1;
         
      } else if (midVal > searchValue) {
         end = mid - 1;
         
      } else if (midVal < searchValue){
         start = mid + 1;
         
      }
   }
   // Return 0 if not found
   return 0;
}

}

Returning row and column positions

If you want the binary search method to return the row and column positions when the search value is found, you need to make the following changes.

  1. Change the method definition to return an array.

    public static int[] binarySearch(int a[][], int searchValue)
  2. Declare an array of size 2 and intialize it with the value -1.

     int[] result = {-1, -1};
  3. If target found, set row and column values and return result.

    if (midVal == searchValue){
    	result[0] = midRow;
    	result[1] = midCol;
    	return result;
    } 
  4. Change the second return statement, to return the initial result array with values -1 in case target value not found.

    return result;
  5. Inside the Main method, change the binarySearch method call to accept result array.

     int[] result = binarySearch(a, target);
     
  6. Finally, print the row and column.

      System.out.println(result[0] + ", "+ result[1]);
      

    You may also add an if.. else block to check row and column equals -1 (Not Found) and print a different message.

Time complexity

The best-case time complexity of binary search algorithm is O(1) when the target search value is the middle of the array. The worst-case is when an search element does not exist and the time complexity is O(log n) where n is the number of elements in the array.


Post a comment

Comments

Nothing yet..be the first to share wisdom.