Implementation of Binary Search Algorithm in Java

In the previous article, we explored the binary search algorithm and wrote pseudocode for both iterative and recursive approaches. Now, it’s time to bring that pseudocode to life by implementing binary search in Java. By the end of this article, you’ll have a working implementation of binary search and a clear understanding of how to use it in your programs.

Prerequisites:

Iterative Implementation of Binary Search in Java

Let’s start with the iterative implementation of the binary search algorithm in Java:


public class BinarySearch {
  public static int binarySearchIterative(int[] arr, int target) {
    // Initialize the search boundaries
    int low = 0;                // First index
    int high = arr.length - 1;  // Last index

    // Keep searching while we have a valid search space
    while (low <= high) {
      // Find the middle element
      int mid = low + (high - low) / 2;
      
      // Check if we found the target
      if (arr[mid] == target) {
        return mid;  // Target found! Return its index
      }
      
      // If not found, eliminate half the search space
      else if (arr[mid] < target) {
        // Target is larger, ignore left half
        low = mid + 1;
      } else {
        // Target is smaller, ignore right half
        high = mid - 1;
      }
    }
    
    // If we get here, target wasn't found
    return -1;
  }
}

Explanation

  1. Initialization: We start with low at the beginning of the array and high at the end.
  2. Loop: The search continues as long as low is less than or equal to high.
  3. Middle Element: We calculate mid and compare arr[mid] with the target.
  4. Update Pointers: Based on the comparison, we adjust low or high.
  5. Return: If the target is found, we return its index. Otherwise, we return -1.

Example Usage

public class BinarySearchExample {
  public static void main(String[] args) {
    // Create a sorted array
    int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    
    // Define the target value we're searching for
    int target = 23;

    // Perform the binary search
    int result = BinarySearch.binarySearchIterative(arr, target);
    
    // Check and display the result
    if (result != -1) {
      System.out.println("Target found at index " + result + ".");
    } else {
      System.out.println("Target not found.");
    }
  }
}

Output:

Target found at index 5.

Recursive Implementation of Binary Search in Java

Now, let’s look at the recursive implementation of the binary search algorithm in Java:


public class BinarySearch {
  public static int binarySearchRecursive(int[] arr, int target, int low, int high) {
    // Base case 1: There is no search space left
    // Which means the target element is not found
    if (low > high) {
      return -1;
    }
    
    // Find middle point
    int mid = low + (high - low) / 2;
    
    // Base case 2: Found the target!
    if (arr[mid] == target) {
      return mid;
    }
    
    // Recursive case 1: Search right half
    else if (arr[mid] < target) {
      return binarySearchRecursive(arr, target, mid + 1, high);
    }
    
    // Recursive case 2: Search left half
    else {
      return binarySearchRecursive(arr, target, low, mid - 1);
    }
  }

  // Helper method to make it easier to use
  public static int binarySearch(int[] arr, int target) {
    return binarySearchRecursive(arr, target, 0, arr.length - 1);
  }
}

Explanation

  1. Base Case: If low exceeds high, the target is not in the array.
  2. Middle Element: We calculate mid and compare arr[mid] with the target.
  3. Recursive Calls:
    • If the target is greater than arr[mid], we search the right half of the current search space.
    • If the target is less than arr[mid], we search the left half of the current search space.
  4. Return: If the target is found, we return its index. Otherwise, we propagate the -1 from the base case.

Example Usage

public class BinarySearchExample {
  public static void main(String[] args) {
    int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target = 23;

    int result = BinarySearch.binarySearch(arr, target);
    if (result != -1) {
      System.out.println("Target found at index " + result + ".");
    } else {
      System.out.println("Target not found.");
    }
  }
}

Output:

Target found at index 5.

Binary Search for Descending Order Lists

So far, we’ve implemented binary search for arrays sorted in ascending order. But what if our array is sorted in descending order? Let’s explore the changes we need to make to our binary search implementations to handle this case.

Changes in the Algorithm

The core logic of binary search remains the same, but we need to adjust our comparisons:

  1. When arr[mid] < target, we now search the left half (instead of right).
  2. When arr[mid] > target, we now search the right half (instead of left).

Iterative Implementation for Descending Order

Here’s how we can modify our iterative implementation for descending order arrays:

public static int binarySearchIterativeDesc(int[] arr, int target) {
  int low = 0;
  int high = arr.length - 1;

  while (low <= high) {
    int mid = low + (high - low) / 2;

    if (arr[mid] == target) {
      return mid;
    } else if (arr[mid] < target) {
      high = mid - 1;  // Search left half
    } else {
      low = mid + 1;   // Search right half
    }
  }

  return -1;
}

Recursive Implementation for Descending Order

Similarly, we can adjust our recursive implementation:

public static int binarySearchRecursiveDesc(int[] arr, int target, int low, int high) {
  if (low > high) {
    return -1;
  }

  int mid = low + (high - low) / 2;

  if (arr[mid] == target) {
    return mid;
  } else if (arr[mid] < target) {
    return binarySearchRecursiveDesc(arr, target, low, mid - 1);
  } else {
    return binarySearchRecursiveDesc(arr, target, mid + 1, high);
  }
}

Example Usage

public class BinarySearchDescExample {
  public static void main(String[] args) {
    int[] arrDesc = {91, 72, 56, 38, 23, 16, 12, 8, 5, 2};
    int target = 23;

    int result = binarySearchIterativeDesc(arrDesc, target);
    if (result != -1) {
      System.out.println("Target found at index " + result + ".");
    } else {
      System.out.println("Target not found.");
    }
  }
}

Output:

Target found at index 4.