Best, Worst और Average Case

#include <iostream>
using namespace std;
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++)
        if (arr[i] == target) return i;
    return -1;
}
int main() {
    int arr[] = {5, 3, 8, 1, 9};
    cout << "Best case (found at 0): " << linearSearch(arr, 5, 5) << endl;
    cout << "Worst case (not found): " << linearSearch(arr, 5, 100) << endl;
    return 0;
}

public class Main {
    static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++)
            if (arr[i] == target) return i;
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 1, 9};
        System.out.println("Best case (found at 0): " + linearSearch(arr, 5));
        System.out.println("Worst case (not found): " + linearSearch(arr, 100));
    }
}

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1

arr = [5, 3, 8, 1, 9]
print("Best case (found at 0):", linear_search(arr, 5))
print("Worst case (not found):", linear_search(arr, 100))

#include <stdio.h>
int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++)
        if (arr[i] == target) return i;
    return -1;
}
int main() {
    int arr[] = {5, 3, 8, 1, 9};
    printf("Best case (found at 0): %d\n", linearSearch(arr, 5, 5));
    printf("Worst case (not found): %d\n", linearSearch(arr, 5, 100));
    return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = 5;
    long totalPositionsChecked = 0;
    for (int target = 0; target < n; target++) {
        for (int i = 0; i <= target; i++) totalPositionsChecked++;
    }
    cout << "Average checks per search: " << (double)totalPositionsChecked / n << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int n = 5;
        long totalPositionsChecked = 0;
        for (int target = 0; target < n; target++)
            for (int i = 0; i <= target; i++) totalPositionsChecked++;
        System.out.println("Average checks per search: " + ((double) totalPositionsChecked / n));
    }
}

n = 5
total_positions_checked = sum(i + 1 for target in range(n) for i in range(target + 1))
print("Average checks per search:", total_positions_checked / n)

#include <stdio.h>
int main() {
    int n = 5;
    long totalPositionsChecked = 0;
    for (int target = 0; target < n; target++)
        for (int i = 0; i <= target; i++) totalPositionsChecked++;
    printf("Average checks per search: %.1f\n", (double)totalPositionsChecked / n);
    return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
    int arr[] = {7, 2, 9, 4, 1};
    // Best case: target is arr[0] -> 1 comparison.
    // Worst case: target is arr[4] or missing -> 5 comparisons.
    cout << "arr[0]=" << arr[0] << " best-case target" << endl;
    cout << "arr[4]=" << arr[4] << " worst-case target" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] arr = {7, 2, 9, 4, 1};
        // Best case: target is arr[0] -> 1 comparison.
        // Worst case: target is arr[4] or missing -> 5 comparisons.
        System.out.println("arr[0]=" + arr[0] + " best-case target");
        System.out.println("arr[4]=" + arr[4] + " worst-case target");
    }
}

arr = [7, 2, 9, 4, 1]
# Best case: target is arr[0] -> 1 comparison.
# Worst case: target is arr[4] or missing -> 5 comparisons.
print("arr[0]=", arr[0], "best-case target")
print("arr[4]=", arr[4], "worst-case target")

#include <stdio.h>
int main() {
    int arr[] = {7, 2, 9, 4, 1};
    /* Best case: arr[0], 1 comparison. Worst case: arr[4] or missing, 5 comparisons. */
    printf("arr[0]=%d best-case target\n", arr[0]);
    printf("arr[4]=%d worst-case target\n", arr[4]);
    return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
    int sortedArr[] = {1, 2, 3, 4, 5};
    // Quicksort on already-sorted input with a bad pivot choice
    // degrades from average O(n log n) to worst-case O(n^2).
    cout << "sortedArr[0]=" << sortedArr[0] << " (adversarial input for quicksort)" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] sortedArr = {1, 2, 3, 4, 5};
        // Quicksort on already-sorted input with a bad pivot choice
        // degrades from average O(n log n) to worst-case O(n^2).
        System.out.println("sortedArr[0]=" + sortedArr[0] + " (adversarial input for quicksort)");
    }
}

sorted_arr = [1, 2, 3, 4, 5]
# Quicksort on already-sorted input with a bad pivot choice
# degrades from average O(n log n) to worst-case O(n^2).
print("sorted_arr[0]=", sorted_arr[0], "(adversarial input for quicksort)")

#include <stdio.h>
int main() {
    int sortedArr[] = {1, 2, 3, 4, 5};
    /* Quicksort on sorted input with a bad pivot degrades to O(n^2). */
    printf("sortedArr[0]=%d (adversarial input for quicksort)\n", sortedArr[0]);
    return 0;
}

Login to try C/C++/Java code in the editor

#include <iostream>
using namespace std;
int main() {
    // Comparing algorithms fairly means looking at best, worst, AND average --
    // not just one case, which can mislead.
    cout << "Best: O(1), Average: O(n), Worst: O(n) -- linear search summary" << endl;
    return 0;
}

public class Main {
    public static void main(String[] args) {
        // Fair comparison needs best, worst, AND average -- not just one case.
        System.out.println("Best: O(1), Average: O(n), Worst: O(n) -- linear search summary");
    }
}

# Fair comparison needs best, worst, AND average -- not just one case.
print("Best: O(1), Average: O(n), Worst: O(n) -- linear search summary")

#include <stdio.h>
int main() {
    /* Fair comparison needs best, worst, AND average -- not just one case. */
    printf("Best: O(1), Average: O(n), Worst: O(n) -- linear search summary\n");
    return 0;
}

Login to try C/C++/Java code in the editor