Binary Search Interactive and Recursive in Java

  2. HowTo
  3. Java Howtos
  4. Binary Search Interactive and Recursive …
Harshit Jindal Feb 02, 2024
Java Java Algorithm
  1. Iterative Binary Search Algorithm
  2. Java Iterative Program for Binary Search
  3. Recursive Binary Search Algorithm
  4. Java Recursive Program for Binary Search
  5. Java Internal Arrays.binarySearch() Overview
  6. Java Program for Binary Search
Binary Search Interactive and Recursive in Java
Note
If you want to understand Binary Search in detail then refer to the binary search algorithm article.

Iterative Binary Search Algorithm

Let us assume that we have an unsorted array A[] containing n elements, and we want to find an element X.

  • Set lo as 0 and hi as n - 1.
  • While lo < hi:
    • Set mid = lo + (hi - lo)/2.
    • If A[mid] == X , we have found the element return the index mid.
    • If A[mid] < X ,then discard the left half of elements and set lo as mid+1.
    • Else if A[mid] > X, then discard the right half of elements and set hi as mid-1.
  • Element is not found, so return -1.
class BinarySearch {
  int binarySearch(int arr[], int x) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;

      if (arr[mid] == x)
        return mid;

      if (arr[mid] < x)
        lo = mid + 1;

      else
        hi = mid - 1;
    }
    return -1;
  }

  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int arr[] = {1, 2, 3, 4, 5};
    int n = arr.length;
    int x = 5;
    int position = ob.binarySearch(arr, x);
    if (position == -1)
      System.out.println("Element not present");
    else
      System.out.println("Element found at index: " + position);
  }
}

Output:

Element found at index: 4

Recursive Binary Search Algorithm

Let us assume that we have an unsorted array A[] containing n elements, and we want to find an element X.

  • Initialize lo as 0 and hi as n-1.
  • if lo >hi, we have exhausted the array search space, return -1.
  • Calculate midpoint mid as lo+(hi-lo)/2. It divides the array into two parts: the lower half with elements from 0 to mid - 1, and the upper half with elements from mid to n - 1.
  • If X == mid, we have found the target element return mid.
  • If X is less than mid, search the lower half of the array by recursively calling binarysearch(arr, lo, mid-1).
  • Else if X is greater than mid, search the upper half of the array by recursively calling binarysearch(arr, mid+1, hi).
class BinarySearch {
  int binarySearch(int arr[], int lo, int hi, int x) {
    if (hi >= lo && lo < arr.length - 1) {
      int mid = lo + (hi - lo) / 2;
      if (arr[mid] == x)
        return mid;
      if (arr[mid] > x)
        return binarySearch(arr, lo, mid - 1, x);
      return binarySearch(arr, mid + 1, hi, x);
    }
    return -1;
  }
  public static void main(String args[]) {
    BinarySearch ob = new BinarySearch();
    int arr[] = {1, 2, 3, 4, 5};
    int n = arr.length;
    int x = 2;
    int position = ob.binarySearch(arr, 0, n - 1, x);
    if (position == -1)
      System.out.println("Element not found !!!");
    else
      System.out.println("Element found at index: " + position);
  }
}

Output:

Element found at index: 1

Java Internal Arrays.binarySearch() Overview

Java provides us with a ready to use function Arrays.binarySearch() so that we don’t have to implement the function ourselves. It is a very simple to use and efficiently implemented method and it is not prone to errors.

Syntax

public static int binarySearch(T arr, T key)

T can be any of the following: int, float, short, long, byte, char, double, and even a user-defined Object as well.

Just like our implemented binary search, it also requires the array to be sorted otherwise the results are undefined. It searches the array using the binary search algorithm and finds the index of the target element. If there are multiple occurrences of the target element then it can return the index of any one of them.

Parameters
Arr The input array
Key The target element we are searching for.

Return

If it finds the target element then it returns its index. Otherwise, it returns beg - 1 where beg is the starting index of the array search space.

import java.util.Arrays;

class BinarySearchExample {
  public static void main(String args[]) {
    int arr[] = {1, 2, 3, 4, 5};
    int key = 2;
    int result = Arrays.binarySearch(arr, key);
    if (result < 0)
      System.out.println("Element is not found!");
    else
      System.out.println("Element is found at index: " + result);
  }
}

Output:

Element is found at index: 1
Author: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Related Article - Java Algorithm