Mastering Binary Search in JavaScript and Java: A Step-by-Step Guide

Binary search is a fundamental algorithm every developer should understand, offering a highly efficient way to search for elements in a sorted array. This algorithm relies on a "divide and conquer" approach, allowing it to halve the search space with each step. In this article, we’ll explore binary search in both JavaScript and Java, covering iterative and recursive implementations.

What is Binary Search?

Binary search is an algorithm designed to find the position of a target value within a sorted array. By leveraging the sorted nature of the array, binary search efficiently narrows down the search space, achieving a time complexity of O(log n). This is much faster than a linear search in large datasets.

Here’s a high-level overview:

1. Start with two pointers, startIndex and endIndex, representing the current search range.
2. Calculate the middle index (midIndex) between startIndex and endIndex.
3. Compare the middle element to the target:
   • If it matches the target, return the index.
   • If the middle element is greater than the target, the target must be in the left half, so adjust endIndex.
   • If the middle element is less than the target, the target must be in the right half, so adjust startIndex.
4. Repeat the process until the target is found or startIndex surpasses endIndex, indicating the target isn’t in the array.

Let’s dive into the code examples.

Iterative Binary Search in JavaScript and Java

JavaScript Implementation

In JavaScript, the iterative approach uses a loop to perform binary search. Here’s what it looks like:

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Java Implementation

In Java, the iterative implementation is quite similar, with adjustments for Java syntax:

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

Explanation

In both implementations:

• We set startIndex and endIndex to the beginning and end of the array, respectively.
• Each iteration finds the middle index, midIndex, and compares arr[midIndex] to the target.
  • If arr[midIndex] equals target, we return midIndex.
  • If arr[midIndex] is less than target, we move startIndex to midIndex 1, narrowing the search to the right half.
  • If arr[midIndex] is greater than target, we move endIndex to midIndex - 1, narrowing the search to the left half.
• The loop exits if startIndex exceeds endIndex, meaning the target isn’t in the array.

Recursive Binary Search in JavaScript and Java

For the recursive approach, we define the function so that it calls itself with updated indices until the target is found or the search range is empty.

JavaScript Implementation

In JavaScript, here’s a recursive binary search implementation:

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Java Implementation

In Java, a similar recursive binary search can be implemented as follows:

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

How the Recursive Version Works

In each recursive call:

• The middle index, midIndex, is calculated.
• If arr[midIndex] matches the target, it returns the index.
• If arr[midIndex] is greater than the target, the search continues in the left half (endIndex becomes midIndex - 1).
• If arr[midIndex] is less than the target, the search continues in the right half (startIndex becomes midIndex 1).
• The base case if (startIndex > endIndex) ensures the recursion stops if the target isn’t found.

  ---

  Complexity Analysis

  • Time Complexity: Both the iterative and recursive versions have a time complexity of O(log n), as each step halves the search space.
  • Space Complexity: The iterative approach is O(1) for space, while the recursive approach has a space complexity of O(log n) due to the call stack.

  When to Use Binary Search

  Binary search is ideal when:

  • The array is sorted: Binary search only works on sorted arrays.
  • Efficiency is critical: Its O(log n) time complexity is highly efficient for large datasets.

  If the array is unsorted, consider sorting it first (at an O(n log n) cost) or using a linear search if the dataset is small.

  ---

  Conclusion

  Binary search is a versatile and efficient algorithm for locating elements in sorted arrays. Whether you choose the iterative or recursive approach, understanding binary search is valuable for improving the performance of your applications. Try out both implementations in JavaScript and Java to get a feel for how they work, and see which fits best for your specific use case.

  ---

  ? Reference

  • Binary Search
  • Grookking Algorithms
  • Big O Notation

  ? Talk to me

  • LinkedIn
  • Github
  • Portfolio

  The above is the detailed content of Mastering Binary Search in JavaScript and Java: A Step-by-Step Guide. For more information, please follow other related articles on the PHP Chinese website!