Searching: linear and binary

Finding a value

• A common job is to search: is a value in an array, and where?
• The usual answer is the index where we found it, or -1 if it is not there.
• We learn two ways: linear search (works on any array) and binary search (needs a sorted array, but is much faster).

Linear search

• Look at each item from index 0 to the end.
• If the item equals the target, return its index right away.
• If the loop finishes with no match, return -1.

public class Main {
    public static void main(String[] args) {
        int[] a = {4, 8, 15, 16, 23};
        int target = 15;
        int found = -1;
        for (int i = 0; i < a.length; i++) {
            if (a[i] == target) {
                found = i;
                break;       // stop early, we have it
            }
        }
        System.out.println(found);   // 2
    }
}

How fast is linear search?

• In the worst case (the value is last, or missing) it checks every item.
• For a list of n items that is up to n checks. We call this linear time.
• For small arrays this is totally fine. For huge sorted arrays we can do better.

Binary search needs a sorted array

• Binary search only works when the array is already sorted (small to large).
• It checks the middle item, then throws away half the array each step.
• That is much faster: a million items take about 20 checks, not a million.

The binary search idea

• Keep two bounds: low (start) and high (end).
• Look at the middle index mid = (low + high) / 2.
• If a[mid] equals the target, return mid.
• If a[mid] is too small, the target must be on the right, so set low = mid + 1.
• If a[mid] is too big, the target must be on the left, so set high = mid - 1.
• Stop when low passes high; then the value is not there, return -1.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12, 16, 23, 38};   // sorted!
        int target = 16;

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;     // go right
            } else {
                high = mid - 1;    // go left
            }
        }
        System.out.println(found);   // 4
    }
}

When a value is missing

• Both searches return -1 when the target is not in the array.
• For binary search, the loop ends when low > high — the bounds have crossed, so there is nowhere left to look.
• Always handle the -1 case in code that calls a search.

public class Main {
    public static void main(String[] args) {
        int[] a = {2, 5, 8, 12};   // sorted
        int target = 7;            // not in the array

        int low = 0;
        int high = a.length - 1;
        int found = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == target) {
                found = mid;
                break;
            } else if (a[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        System.out.println(found);   // -1
    }
}

Now you try

• Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
• Press Run to compile and run, then Check answer.
• Your code compiles and runs on the server, so even the first run is fast.