WebsiteLogo

Binary Search in Java: Theory and Applications

In-depth exploration of binary search algorithm in Java, including iterative and recursive implementations, and its applications in problem-solving.

⬅ Previous Next ➡

Iterative Binary Search Implementation in Java

Explanation of Iterative Binary Search

Binary search is a highly efficient search algorithm used to find the position of a target value within a sorted array. The iterative version achieves the same result as the recursive version, but uses loops instead of recursion, which can be more efficient in some cases due to avoiding function call overhead. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the left half. If the target value is greater than the middle element, the search continues in the right half. This process continues until the target value is found or the search interval is empty.

Key Concepts:

  • Sorted Array: Binary search requires the array to be sorted.
  • Divide and Conquer: The algorithm repeatedly divides the search interval.
  • Efficiency: Binary search has a time complexity of O(log n), which is significantly faster than linear search (O(n)) for large datasets.

Step-by-Step Guide to Implementing Iterative Binary Search in Java

  1. Initialization

    Initialize two pointers: low and high. low points to the beginning of the array (index 0), and high points to the end of the array (index array.length - 1). 

    int low = 0;
int high = array.length - 1;

  2. Iteration

    Use a while loop that continues as long as low is less than or equal to high. This condition ensures that the search interval is not empty. 

    while (low <= high) {
    // Search within the interval [low, high]
}

  3. Calculate the Middle Index

    Inside the loop, calculate the middle index mid. To prevent potential integer overflow issues with large arrays, calculate mid as: 

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

    Instead of (low + high) / 2, using low + (high - low) / 2 avoids potential integer overflow if low + high exceeds the maximum value of an integer.

  4. Compare the Middle Element with the Target

    Compare the element at index mid (array[mid]) with the target value.

    • If array[mid] is equal to the target, the target is found, and you can return the index mid.
    • If array[mid] is less than the target, the target must be in the right half of the array. Update low to mid + 1.
    • If array[mid] is greater than the target, the target must be in the left half of the array. Update high to mid - 1.

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

  5. Target Not Found

    If the while loop finishes without finding the target (i.e., low becomes greater than high), it means the target is not present in the array. Return a value (usually -1) to indicate that the target was not found. 

    return -1; // Target not found

Detailed Code Example

public class BinarySearch {

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

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

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

    return -1; // Target not found
}

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

    if (index != -1) {
        System.out.println("Target " + target + " found at index " + index);
    } else {
        System.out.println("Target " + target + " not found in the array");
    }
}
}

Explanation: This code defines a class BinarySearch with a method iterativeBinarySearch that implements the iterative binary search algorithm. The main method demonstrates how to use the iterativeBinarySearch method. It initializes a sorted array and a target value, then calls iterativeBinarySearch to find the target's index. Finally, it prints whether the target was found and, if so, its index.

Binary Search in Competitive Programming in Java with Solutions

Binary Search is frequently used in competitive programming for optimization. It helps reduce the search space, leading to more efficient solutions. Here are some common application scenarios and an example.

Common Application Scenarios:

  • Finding the Minimum/Maximum Value satisfying a Condition: If a condition is monotonic (i.e., if a value satisfies it, all values greater/smaller also do), Binary Search can efficiently find the minimum/maximum satisfying value.
  • Finding the First/Last Occurrence of an Element: In a sorted array with duplicate elements, Binary Search can be adapted to find the first or last occurrence.
  • Optimizing Search in Sorted Data: Whenever you need to search for an element in a sorted dataset, consider Binary Search.

Example Problem:

Problem Statement: Given a sorted array of integers and a number `x`, find the index of the first element in the array that is greater than or equal to `x`. If no such element exists, return the size of the array.

Solution:

import java.util.*;
import java.lang.*;

class FirstElementNotLessThanX {
    public static int findFirstElementNotLessThanX(int[] arr, int x) {
    int low = 0;
    int high = arr.length - 1;
    int ans = arr.length; // Initialize ans to arr.length in case no element >= x is found

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

        if (arr[mid] >= x) {
            ans = mid;   // Possible answer, try to find a smaller index
            high = mid - 1; // Search left
        } else {
            low = mid + 1; // Search right
        }
    }

    return ans;
}

public static void main(String[] args) {
    int[] arr = {2, 3, 6, 8, 11, 11, 15};
    int x = 7;
    int index = findFirstElementNotLessThanX(arr, x);

    System.out.println("Index of first element not less than " + x + ": " + index); // Output: 3
}
}

Explanation:

  • The findFirstElementNotLessThanX method uses binary search to find the required element.
  • The ans variable stores the best possible index found so far. It is initialized to arr.length in case no element is found that is greater than or equal to x.
  • If arr[mid] is greater than or equal to x, it updates ans to mid and continues the search in the left half to find an even smaller index that satisfies the condition.
  • If arr[mid] is less than x, it continues the search in the right half.
⬅ Previous Next ➡