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

Binary Search for Object Search

Problem Statement

Write a Java program that extends the Binary Search algorithm to find a Student object by its id in a sorted array of Student objects, where the array is sorted by id in ascending order. The program should count the number of comparisons made during the search and test with a sample dataset, including arrays of different sizes (e.g., 10, 100, 1000) and various target id values (present, absent, middle element). The Student class should have fields id (integer) and name (string), and Binary Search will compare id values to locate the target. You can visualize this as searching for a student by their ID in a sorted roster, halving the search range with each comparison.

Input:

  • A sorted array of Student objects (by id in ascending order) and a target id to find. Output: The index of the Student object with the target id (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.
  • Student id values and target id are integers in the range [1, 10^9].
  • The input array is sorted by id in ascending order. Example:
  • Input: array = [Student(1, "Alice"), Student(3, "Bob"), Student(5, "Charlie"), Student(7, "David")], targetId = 3
  • Output:
    • Input Array: [(1, Alice), (3, Bob), (5, Charlie), (7, David)]
    • Target ID: 3
    • Index: 1
    • Comparisons: 2
  • Explanation: Binary Search finds the Student with id=3 at index 1 after 2 comparisons.
  • Input: array = [Student(1, "Alice"), Student(2, "Bob")], targetId = 4
  • Output:
    • Input Array: [(1, Alice), (2, Bob)]
    • Target ID: 4
    • Index: -1
    • Comparisons: 2
  • Explanation: Binary Search returns -1 as no Student with id=4 is found after 2 comparisons.

Pseudocode

CLASS Student
    DECLARE id as integer
    DECLARE name as string
    FUNCTION toString()
        RETURN "(" + id + ", " + name + ")"
    ENDFUNCTION
ENDCLASS

FUNCTION binarySearch(arr, targetId)
    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].id equals targetId THEN
            RETURN mid, comparisons
        ELSE IF arr[mid].id < targetId 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 student in arr
        APPEND student.toString() to result
        IF student 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, targetId) pairs
        FOR each testCase in testCases
            PRINT test case details
            SET arr to testCase sorted Student array
            SET targetId to testCase target
            CALL binarySearch(arr, targetId) to get index, comparisons
            PRINT input array, targetId, index, comparisons
        ENDFOR
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define Student class: a. Include id (integer) and name (string) fields. b. Provide a toString method to format as (id, name).
  2. Define binarySearch: a. Initialize comparisons to 0, left to 0, right to n-1. b. While left <= right:
    • Compute mid as the floor of (left + right) / 2.
    • Increment comparisons and check if arr[mid].id equals targetId.
    • If equal, return mid and comparisons.
    • If arr[mid].id < targetId, set left to mid + 1.
    • If arr[mid].id > targetId, set right to mid - 1. c. Return -1 and comparisons if not found.
  3. Define toString: a. Convert array of Student objects to a string, limiting output for large arrays.
  4. In main, test with: a. Array sizes: 10, 100, 1000 (sorted by id). b. For each size, test:
    • Target id present in the middle (average case).
    • Target id absent.
    • Target id as the middle element (exact middle). c. Generate sorted Student arrays with unique id values using a fixed seed.

Java Implementation

import java.util.*;

public class BinarySearchObjectSearch {
    // Student class
    static class Student {
        int id;
        String name;

        Student(int id, String name) {
            this.id = id;
            this.name = name;
        }

        @Override
        public String toString() {
            return "(" + id + ", " + name + ")";
        }
    }

    // Performs Binary Search on Student array by id
    public int[] binarySearch(Student[] arr, int targetId) {
        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].id == targetId) {
                return new int[]{mid, comparisons};
            } else if (arr[mid].id < targetId) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return new int[]{-1, comparisons};
    }

    // Converts Student array to string
    public String toString(Student[] 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].toString());
            if (i < limit - 1) {
                result.append(", ");
            }
        }
        if (arr.length > limit) {
            result.append(", ...]");
        } else {
            result.append("]");
        }
        return result.toString();
    }

    // Generates sorted Student array
    private Student[] generateStudentArray(int n) {
        Random rand = new Random(42); // Fixed seed for reproducibility
        Student[] arr = new Student[n];
        String[] names = {"Alice", "Bob", "Charlie", "David", "Eve", "Frank", "Grace", "Hannah", "Ivy", "Jack"};
        // Ensure unique IDs by using a sorted sequence
        for (int i = 0; i < n; i++) {
            int id = i + 1; // IDs from 1 to n
            String name = names[rand.nextInt(names.length)]; // Random name
            arr[i] = new Student(id, name);
        }
        // Array is already sorted by ID
        return arr;
    }

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

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

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

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

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

Output

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

Array Size: 10
Input Array: [(1, Charlie), (2, Alice), (3, Jack), (4, Ivy), (5, Eve), (6, Grace), (7, David), (8, Bob), (9, Hannah), (10, Eve)]
Test case 1: Target present (middle)
Target ID: 6
Index: 5
Comparisons: 2

Test case 2: Target absent
Target ID: 11
Index: -1
Comparisons: 4

Test case 3: Target middle element
Target ID: 5
Index: 4
Comparisons: 3

Array Size: 100
Input Array: [(1, Charlie), (2, Alice), (3, Jack), (4, Ivy), (5, Eve), (6, Grace), (7, David), (8, Bob), (9, Hannah), (10, Eve), ...]
Test case 1: Target present (middle)
Target ID: 51
Index: 50
Comparisons: 7

Test case 2: Target absent
Target ID: 101
Index: -1
Comparisons: 7

Test case 3: Target middle element
Target ID: 50
Index: 49
Comparisons: 7

Array Size: 1000
Input Array: [(1, Charlie), (2, Alice), (3, Jack), (4, Ivy), (5, Eve), (6, Grace), (7, David), (8, Bob), (9, Hannah), (10, Eve), ...]
Test case 1: Target present (middle)
Target ID: 501
Index: 500
Comparisons: 10

Test case 2: Target absent
Target ID: 1001
Index: -1
Comparisons: 10

Test case 3: Target middle element
Target ID: 500
Index: 499
Comparisons: 10

Explanation:

  • Size 10: Finds id=6 at index 5 (~2 comparisons), absent id=11 (~4 comparisons), middle id=5 at index 4 (~3 comparisons).
  • Size 100: Finds id=51 at index 50 (~7 comparisons), absent id=101 (~7 comparisons), middle id=50 at index 49 (~7 comparisons).
  • Size 1000: Finds id=501 at index 500 (~10 comparisons), absent id=1001 (~10 comparisons), middle id=500 at index 499 (~10 comparisons).
  • Comparisons scale logarithmically (~log n) due to Binary Search’s efficiency.

How It Works

  • Student Class:
    • Stores id and name, with a toString method for output formatting.
  • binarySearch:
    • Adapts Binary Search to compare arr[mid].id with targetId.
    • Uses left and right pointers to halve the search range, incrementing comparisons.
    • Returns [index, comparisons] or [-1, comparisons].
  • generateStudentArray:
    • Creates an array of Student objects with unique id values (1 to n) and random names.
  • toString: Formats Student array, limiting to 10 elements.
  • Example Trace (Size 10, Target ID=6):
    • Array: [(1, Charlie), (2, Alice), (3, Jack), (4, Ivy), (5, Eve), (6, Grace), (7, David), (8, Bob), (9, Hannah), (10, Eve)].
    • Initial: left=0, right=9, mid=4, arr[4].id=5 < 6, comparisons=1, left=5.
    • Next: left=5, right=9, mid=7, arr[7].id=8 > 6, comparisons=2, right=6.
    • Next: left=5, right=6, mid=5, arr[5].id=6 = 6, comparisons=3, return [5, 3].
  • Main Method: Tests sizes 10, 100, 1000 with present, absent, and middle id targets, displaying results and comparisons.

Complexity Analysis Table

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

Note:

  • n is the array length.
  • Time complexity: O(log n) for binarySearch (halves search range); O(n) for toString and generateStudentArray (linear iteration).
  • Space complexity: O(1) for binarySearch (constant extra space); O(n) for toString (string builder) and generateStudentArray (array storage).
  • Binary Search remains efficient for object searches when sorted by a key.

✅ Tip: Binary Search can be extended to search for objects by a key (e.g., id) in sorted arrays, maintaining O(log n) efficiency. Ensure the array is sorted by the search key to achieve correct results.

⚠ Warning: The array must be sorted by the id field in ascending order. Incorrect sorting or duplicate id values may lead to unpredictable results. Use unique keys or handle duplicates explicitly if needed.