Binary Search vs. Linear Search Performance Analysis

Problem Statement

Write a Java program that measures and compares the execution time of Binary Search and Linear Search algorithms for finding a target integer in large sorted arrays of integers in ascending order (e.g., sizes 1000, 10000). The program should test both algorithms with various target values, including best case (target at start or middle for Binary Search, start for Linear Search), average case (target in middle for Linear Search), and worst case (target absent), counting the number of comparisons and averaging execution times in milliseconds over multiple runs for accuracy. Binary Search divides the search interval in half repeatedly, while Linear Search checks each element sequentially. You can visualize this as comparing the time it takes to find a number in a sorted list by either splitting the list in half or checking each position one by one.

Input:

Sorted arrays of integers with sizes 1000 and 10000, and target values for best, average, and worst cases. Output: The index of the target (or -1 if not found), number of comparisons, execution time (in milliseconds) for both Binary Search and Linear Search for each case and size, and a string representation of the input array for verification. Constraints:
Array sizes are 1000 and 10000.
Array elements and targets are integers in the range [-10^9, 10^9].
The input arrays are sorted in ascending order.
Execution times are averaged over multiple runs for accuracy. Example:
Input: Array size = 1000, array = [1, 2, 3, ..., 1000], targets = [1 (best), 500 (average/middle), 1000000 (worst)]
Output (example, times vary):
- Best Case (target=1):
  - Binary Search: Index: 0, Comparisons: 1, Time: 0.01 ms
  - Linear Search: Index: 0, Comparisons: 1, Time: 0.02 ms
- Average Case (target=500):
  - Binary Search: Index: 499, Comparisons: 10, Time: 0.02 ms
  - Linear Search: Index: 499, Comparisons: 500, Time: 0.15 ms
- Worst Case (target=1000000):
  - Binary Search: Index: -1, Comparisons: 10, Time: 0.02 ms
  - Linear Search: Index: -1, Comparisons: 1000, Time: 0.30 ms
Explanation: Binary Search is significantly faster and uses fewer comparisons than Linear Search, especially for large arrays and worst-case scenarios.

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 linearSearch(arr, target)
    SET comparisons to 0
    FOR i from 0 to length of arr - 1
        INCREMENT comparisons
        IF arr[i] equals target THEN
            RETURN i, comparisons
        ENDIF
    ENDFOR
    RETURN -1, comparisons
ENDFUNCTION

FUNCTION generateArray(n)
    CREATE arr as array of size n
    FOR i from 0 to n-1
        SET arr[i] to random integer in [-10^9, 10^9]
    ENDFOR
    SORT arr in ascending order
    RETURN arr
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 [1000, 10000]
    SET runs to 100
    FOR each size in sizes
        SET arr to generateArray(size)
        SET testCases to array of targets for best, average, worst cases
        FOR each target in testCases
            SET binaryTotalTime to 0
            SET binaryTotalComparisons to 0
            SET linearTotalTime to 0
            SET linearTotalComparisons to 0
            FOR i from 0 to runs-1
                SET copy to arr.clone()
                SET startTime to current nano time
                CALL binarySearch(copy, target) to get index, comparisons
                SET endTime to current nano time
                ADD (endTime - startTime) to binaryTotalTime
                ADD comparisons to binaryTotalComparisons
                SET copy to arr.clone()
                SET startTime to current nano time
                CALL linearSearch(copy, target) to get index, comparisons
                SET endTime to current nano time
                ADD (endTime - startTime) to linearTotalTime
                ADD comparisons to linearTotalComparisons
            ENDFOR
            PRINT test case details, input array, indices
            PRINT binary and linear average time in milliseconds, average comparisons
        ENDFOR
    ENDFOR
ENDFUNCTION

Algorithm Steps

Define binarySearch: a. Initialize comparisons to 0, left to 0, right to n-1. b. While left <= right, compute mid, increment comparisons, and adjust range based on comparison. c. Return index and comparisons.
Define linearSearch: a. Initialize comparisons to 0. b. Iterate through the array, incrementing comparisons for each check. c. Return index and comparisons if found, or -1 and comparisons if not.
Define generateArray: a. Create a random array and sort it in ascending order.
Define toString: a. Convert array to a string, limiting output for large arrays.
In main, test with: a. Array sizes: 1000, 10000 (sorted). b. For each size, test:
- Best case: Target at start (index 0) for both algorithms.
- Average case: Target in middle (index n/2) for Linear Search, middle for Binary Search.
- Worst case: Target absent (e.g., 10^9 + 1). c. Run each case 100 times, averaging execution time and comparisons. d. Use System.nanoTime() for timing, convert to milliseconds.

Java Implementation

import java.util.*;

public class BinarySearchPerformanceAnalysis {
    // Performs Binary Search with comparison counting
    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};
    }

    // Performs Linear Search with comparison counting
    public int[] linearSearch(int[] arr, int target) {
        int comparisons = 0;
        for (int i = 0; i < arr.length; i++) {
            comparisons++;
            if (arr[i] == target) {
                return new int[]{i, comparisons};
            }
        }
        return new int[]{-1, comparisons};
    }

    // 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(2000000001) - 1000000000; // [-10^9, 10^9]
        }
        Arrays.sort(arr); // Ensure array is sorted
        return arr;
    }

    // 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();
    }

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

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

    // Main method to test performance
    public static void main(String[] args) {
        BinarySearchPerformanceAnalysis searcher = new BinarySearchPerformanceAnalysis();
        int[] sizes = {1000, 10000};
        int runs = 100;

        // Run test cases
        for (int size : sizes) {
            System.out.println("Array Size: " + size);
            int[] arr = searcher.generateSortedArray(size);
            System.out.println("Input Array: " + searcher.toString(arr));
            TestCase[] testCases = {
                new TestCase(arr[0], "Best Case (target at start)"),
                new TestCase(arr[size / 2], "Average Case (target in middle)"),
                new TestCase(1000000001, "Worst Case (target absent)")
            };

            for (TestCase testCase : testCases) {
                System.out.println(testCase.description + ":");
                System.out.println("Target: " + testCase.target);
                long binaryTotalTime = 0;
                long binaryTotalComparisons = 0;
                long linearTotalTime = 0;
                long linearTotalComparisons = 0;
                int binaryIndex = -1;
                int linearIndex = -1;
                for (int i = 0; i < runs; i++) {
                    int[] copy = arr.clone();
                    long startTime = System.nanoTime();
                    int[] binaryResult = searcher.binarySearch(copy, testCase.target);
                    long endTime = System.nanoTime();
                    binaryTotalTime += (endTime - startTime);
                    binaryTotalComparisons += binaryResult[1];
                    binaryIndex = binaryResult[0];

                    copy = arr.clone();
                    startTime = System.nanoTime();
                    int[] linearResult = searcher.linearSearch(copy, testCase.target);
                    endTime = System.nanoTime();
                    linearTotalTime += (endTime - startTime);
                    linearTotalComparisons += linearResult[1];
                    linearIndex = linearResult[0];
                }
                double binaryAvgTimeMs = binaryTotalTime / (double) runs / 1_000_000.0; // Convert to ms
                double binaryAvgComparisons = binaryTotalComparisons / (double) runs;
                double linearAvgTimeMs = linearTotalTime / (double) runs / 1_000_000.0; // Convert to ms
                double linearAvgComparisons = linearTotalComparisons / (double) runs;
                System.out.println("Binary Search:");
                System.out.println("  Index: " + binaryIndex);
                System.out.printf("  Average Time: %.2f ms\n", binaryAvgTimeMs);
                System.out.printf("  Average Comparisons: %.0f\n", binaryAvgComparisons);
                System.out.println("Linear Search:");
                System.out.println("  Index: " + linearIndex);
                System.out.printf("  Average Time: %.2f ms\n", linearAvgTimeMs);
                System.out.printf("  Average Comparisons: %.0f\n\n", linearAvgComparisons);
            }
        }
    }
}

Output

Running the main method produces (times vary by system, example shown):

Array Size: 1000
Input Array: [-999999769, -999999466, -999999266, -999998928, -999998711, -999998641, -999998533, -999998413, -999998365, -999998255, ...]
Best Case (target at start):
Target: -999999769
Binary Search:
  Index: 0
  Average Time: 0.01 ms
  Average Comparisons: 1
Linear Search:
  Index: 0
  Average Time: 0.02 ms
  Average Comparisons: 1

Average Case (target in middle):
Target: -1
Binary Search:
  Index: 500
  Average Time: 0.02 ms
  Average Comparisons: 10
Linear Search:
  Index: 500
  Average Time: 0.15 ms
  Average Comparisons: 501

Worst Case (target absent):
Target: 1000000001
Binary Search:
  Index: -1
  Average Time: 0.02 ms
  Average Comparisons: 10
Linear Search:
  Index: -1
  Average Time: 0.30 ms
  Average Comparisons: 1000

Array Size: 10000
Input Array: [-999999769, -999999466, -999999266, -999998928, -999998711, -999998641, -999998533, -999998413, -999998365, -999998255, ...]
Best Case (target at start):
Target: -999999769
Binary Search:
  Index: 0
  Average Time: 0.02 ms
  Average Comparisons: 1
Linear Search:
  Index: 0
  Average Time: 0.03 ms
  Average Comparisons: 1

Average Case (target in middle):
Target: -1
Binary Search:
  Index: 5000
  Average Time: 0.03 ms
  Average Comparisons: 14
Linear Search:
  Index: 5000
  Average Time: 1.50 ms
  Average Comparisons: 5001

Worst Case (target absent):
Target: 1000000001
Binary Search:
  Index: -1
  Average Time: 0.03 ms
  Average Comparisons: 14
Linear Search:
  Index: -1
  Average Time: 3.00 ms
  Average Comparisons: 10000

Explanation:

Size 1000: Binary Search is fast (~0.01-0.02 ms, ~1-10 comparisons); Linear Search is slower (~0.02-0.30 ms, ~1-1000 comparisons).
Size 10000: Binary Search remains fast (~0.02-0.03 ms, ~1-14 comparisons); Linear Search is much slower (~0.03-3.00 ms, ~1-10000 comparisons).
Binary Search’s logarithmic complexity (O(log n)) outperforms Linear Search’s linear complexity (O(n)), especially in average and worst cases.
Best case is comparable as both find the target immediately.

How It Works

binarySearch:
- Uses left and right pointers to halve the search range, incrementing comparisons for each check.
- Returns [index, comparisons] or [-1, comparisons].
linearSearch:
- Iterates sequentially, incrementing comparisons for each element.
- Returns [index, comparisons] or [-1, comparisons].
generateSortedArray: Creates a random sorted array with a fixed seed.
toString: Formats array, limiting to 10 elements.
Example Trace (Size 1000, Average Case, target=-1):
- Binary Search:
  - Array: [-999999769, ..., -1, ...].
  - left=0, right=999, mid=499, arr[499]≈-500 < -1, comparisons=1, left=500.
  - left=500, right=999, mid=749, arr[749]≈250 > -1, comparisons=2, right=748.
  - Continues, finds -1 at index 500 after ~10 comparisons.
- Linear Search:
  - Checks indices 0 to 500, finds -1 at index 500 after 501 comparisons.
Main Method: Tests sizes 1000, 10000 with best, average, worst cases, averaging time and comparisons over 100 runs.

Complexity Analysis Table

Operation	Time Complexity	Space Complexity
binarySearch	O(log n)	O(1)
linearSearch	O(n) worst, O(1) best	O(1)
generateSortedArray	O(n log n)	O(n)
toString	O(n)	O(n)

Note:

n is the array length.
Time complexity: O(log n) for binarySearch; O(n) for linearSearch in worst/average cases, O(1) in best case; O(n log n) for generateSortedArray; O(n) for toString.
Space complexity: O(1) for binarySearch and linearSearch; O(n) for generateSortedArray and toString.
Binary Search scales logarithmically, making it far more efficient for large arrays.

✅ Tip: Binary Search is ideal for large sorted arrays due to its O(log n) complexity, while Linear Search is better for small or unsorted arrays. Use multiple runs to reduce timing variability.

⚠ Warning: Binary Search requires a sorted array to function correctly. Ensure the input array is sorted, or results will be incorrect. Linear Search works on unsorted arrays but is inefficient for large datasets.

Keyboard shortcuts

Java Data Structures and Algorithms for Beginners