Hồ Quốc Trí

1. Linear search
Time:
- Worst: O(n)
- Average:
- Best:

Code:
public class LinearSearchExample {
   
    private static int[] a = {1000, 11, 50, 1, 2, 3, 78, 100, 101, 102, 1000, 1000};
   
    public static void main(String[] args) {
        int x = 1000;
        int count = 0;
       
        for (int i = 0; i < a.length; i++) {
            if (a[i] == x) {
                count++;
            }
        }
       
        if (count == 0) {
            System.out.println("not found");
        } else {
            System.out.println("Match results: " + count);
        }
    }
}

2. Binary search
Time:
- Worst:O (log n)
- Average:
- Best:

Code:
public class BinarySearchExample {

    // sorted array
    private static int[] a = { 10, 21, 23, 54, 61, 72 };

    public static void main(String[] args) {
        int x = 10;

        // sort array
        int left = 0;
        int right = a.length;
        int mid;
        while (left <= right) {
            mid = (left + right - 1) / 2;

            if (a[mid] == x) {
                System.out.println("Found " + x + " in array.");
                break;
            } else if (a[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

    }
}

Read more…