Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Basic Binary Search

Problem Statement

Write a Java program that implements the Binary Search algorithm to find a target integer in a sorted array of integers in ascending order. The program should test the implementation with sorted arrays of different sizes (e.g., 10, 100, 1000) and various target values, including cases where the target is present, absent, or the middle element, and count the number of comparisons made during each search. Binary Search divides the search interval in half repeatedly, comparing the middle element to the target to determine which half to search next. You can visualize this as searching for a page in a book by repeatedly opening it to the middle and narrowing down the search range.

Input:

  • A sorted array of integers (ascending order) and a target integer to find. Output: The index of the target (or -1 if not found), the number of comparisons made, and a string representation of the input array for verification. Constraints:
  • The array length n is between 0 and 10^5.
  • Array elements and target are integers in the range [-10^9, 10^9].
  • The input array is sorted in ascending order. Example:
  • Input: array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target = 7
  • Output:
    • Input Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
    • Target: 7
    • Index: 3
    • Comparisons: 2
  • Explanation: Binary Search checks the middle element, narrows to the left half, and finds 7 at index 3 after 2 comparisons.
  • Input: array = [1, 2, 3], target = 4
  • Output:
    • Input Array: [1, 2, 3]
    • Target: 4
    • Index: -1
    • Comparisons: 2
  • Explanation: Binary Search checks the middle, narrows the range, and returns -1 as 4 is not found after 2 comparisons.

Pseudocode

FUNCTION binarySearch(arr, target)
    SET comparisons to 0
    SET left to 0
    SET right to length of arr - 1
    WHILE left <= right
        SET mid to floor((left + right) / 2)
        INCREMENT comparisons
        IF arr[mid] equals target THEN
            RETURN mid, comparisons
        ELSE IF arr[mid] < target THEN
            SET left to mid + 1
        ELSE
            SET right to mid - 1
        ENDIF
    ENDWHILE
    RETURN -1, comparisons
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET sizes to [10, 100, 1000]
    FOR each size in sizes
        SET testCases to array of (array, target) pairs
        FOR each testCase in testCases
            PRINT test case details
            SET arr to testCase sorted array
            SET target to testCase target
            CALL binarySearch(arr, target) to get index, comparisons
            PRINT input array, target, index, comparisons
        ENDFOR
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define binarySearch: a. Initialize a comparisons counter to 0, left to 0, and right to n-1. b. While left <= right:
    • Compute mid as the floor of (left + right) / 2.
    • Increment comparisons and check if arr[mid] equals the target.
    • If equal, return mid and comparisons.
    • If arr[mid] < target, set left to mid + 1.
    • If arr[mid] > target, set right to mid - 1. c. Return -1 and comparisons if not found.
  2. Define toString: a. Convert array to a string, limiting output for large arrays.
  3. In main, test with: a. Array sizes: 10, 100, 1000 (sorted in ascending order). b. For each size, test:
    • Target present in the middle (average case).
    • Target absent (worst case).
    • Target as the middle element (exact middle). c. Generate sorted arrays with a fixed seed for reproducibility.

Java Implementation

import java.util.*;

public class BasicBinarySearch {
    // Performs Binary Search and counts comparisons
    public int[] binarySearch(int[] arr, int target) {
        int comparisons = 0;
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // Avoid overflow
            comparisons++;
            if (arr[mid] == target) {
                return new int[]{mid, comparisons};
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return new int[]{-1, comparisons};
    }

    // Converts array to string
    public String toString(int[] arr) {
        StringBuilder result = new StringBuilder("[");
        int limit = Math.min(arr.length, 10); // Limit output for large arrays
        for (int i = 0; i < limit; i++) {
            result.append(arr[i]);
            if (i < limit - 1) {
                result.append(", ");
            }
        }
        if (arr.length > limit) {
            result.append(", ...]");
        } else {
            result.append("]");
        }
        return result.toString();
    }

    // Generates sorted array
    private int[] generateSortedArray(int n) {
        Random rand = new Random(42); // Fixed seed for reproducibility
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(2001) - 1000; // [-1000, 1000]
        }
        Arrays.sort(arr); // Ensure array is sorted
        return arr;
    }

    // Helper class for test cases
    static class TestCase {
        int[] arr;
        int target;
        String description;

        TestCase(int[] arr, int target, String description) {
            this.arr = arr;
            this.target = target;
            this.description = description;
        }
    }

    // Main method to test Binary Search
    public static void main(String[] args) {
        BasicBinarySearch searcher = new BasicBinarySearch();
        int[] sizes = {10, 100, 1000};

        // Run test cases
        for (int size : sizes) {
            System.out.println("Array Size: " + size);
            int[] arr = searcher.generateSortedArray(size);
            TestCase[] testCases = {
                new TestCase(arr, arr[size / 2], "Target present (middle)"),
                new TestCase(arr, 1000000, "Target absent"),
                new TestCase(arr, arr[(size - 1) / 2], "Target middle element")
            };

            for (int i = 0; i < testCases.length; i++) {
                System.out.println("Test case " + (i + 1) + ": " + testCases[i].description);
                int[] sortedArr = testCases[i].arr.clone(); // Copy to preserve original
                int target = testCases[i].target;
                System.out.println("Input Array: " + searcher.toString(sortedArr));
                System.out.println("Target: " + target);
                int[] result = searcher.binarySearch(sortedArr, target);
                System.out.println("Index: " + result[0]);
                System.out.println("Comparisons: " + result[1] + "\n");
            }
        }
    }
}

Output

Running the main method produces (example output, random values fixed by seed):

Array Size: 10
Test case 1: Target present (middle)
Input Array: [-766, -628, -333, 289, 304, 360, 374, 648, 727, 767]
Target: 360
Index: 5
Comparisons: 2

Test case 2: Target absent
Input Array: [-766, -628, -333, 289, 304, 360, 374, 648, 727, 767]
Target: 1000000
Index: -1
Comparisons: 4

Test case 3: Target middle element
Input Array: [-766, -628, -333, 289, 304, 360, 374, 648, 727, 767]
Target: 304
Index: 4
Comparisons: 3

Array Size: 100
Test case 1: Target present (middle)
Input Array: [-1000, -996, -995, -994, -987, -986, -985, -984, -983, -982, ...]
Target: -500
Index: 50
Comparisons: 7

Test case 2: Target absent
Input Array: [-1000, -996, -995, -994, -987, -986, -985, -984, -983, -982, ...]
Target: 1000000
Index: -1
Comparisons: 7

Test case 3: Target middle element
Input Array: [-1000, -996, -995, -994, -987, -986, -985, -984, -983, -982, ...]
Target: -500
Index: 50
Comparisons: 7

Array Size: 1000
Test case 1: Target present (middle)
Input Array: [-1000, -996, -995, -994, -987, -986, -985, -984, -983, -982, ...]
Target: -1
Index: 500
Comparisons: 10

Test case 2: Target absent
Input Array: [-1000, -996, -995, -994, -987, -986, -985, -984, -983, -982, ...]
Target: 1000000
Index: -1
Comparisons: 10

Test case 3: Target middle element
Input Array: [-1000, -996, -995, -994, -987, -986, -985, -984, -983, -982, ...]
Target: -1
Index: 500
Comparisons: 10

Explanation:

  • Size 10: Finds middle target in ~2-3 comparisons, absent target in ~4, middle element in ~3.
  • Size 100: Finds middle target in ~7 comparisons, absent target in ~7, middle element in ~7.
  • Size 1000: Finds middle target in ~10 comparisons, absent target in ~10, middle element in ~10.
  • Binary Search is efficient, with comparisons scaling logarithmically (~log n).

How It Works

  • binarySearch:
    • Uses left and right pointers to maintain the search range.
    • Computes mid and increments comparisons for each check.
    • Adjusts range based on whether arr[mid] is less than or greater than the target.
    • Returns [index, comparisons] or [-1, comparisons].
  • generateSortedArray: Creates a random array, sorts it in ascending order.
  • toString: Formats array, limiting output to 10 elements.
  • Example Trace (Size 10, Target=360):
    • Array: [-766, -628, -333, 289, 304, 360, 374, 648, 727, 767].
    • Initial: left=0, right=9, mid=4, arr[4]=304 < 360, comparisons=1, set left=5.
    • Next: left=5, right=9, mid=7, arr[7]=648 > 360, comparisons=2, set right=6.
    • Next: left=5, right=6, mid=5, arr[5]=360 = 360, comparisons=3, return [5, 3].
  • Main Method: Tests sizes 10, 100, 1000 with targets in the middle, absent, and exact middle, displaying results and comparisons.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
binarySearchO(log n)O(1)
toStringO(n)O(n)
generateSortedArrayO(n log n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(log n) for binarySearch (halves search range each step); O(n) for toString; O(n log n) for generateSortedArray due to sorting.
  • Space complexity: O(1) for binarySearch (constant extra space); O(n) for toString (string builder) and generateSortedArray (array storage).
  • Binary Search is efficient for sorted arrays but requires sorting if the input is unsorted.

✅ Tip: Binary Search is highly efficient for sorted arrays, with O(log n) comparisons. Ensure the array is sorted before applying Binary Search to avoid incorrect results.

⚠ Warning: Binary Search requires the input array to be sorted in ascending order. Applying it to an unsorted array will produce incorrect results. Always verify the array’s sorted state.