Searching and Sorting

Algorithms: Searching, Sorting, and Recursion

By the end of this lesson, you will be able to implement and trace linear and binary search, implement selection and insertion sort, write recursive methods, and analyze algorithm efficiency.

Searching Algorithms

Linear Search

Algorithm: check each element one by one from the start until the target is found or the array is exhausted.

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;  // found — return index
        }
    }
    return -1;  // not found
}

Time complexity: O(n) — in the worst case, must check every element.

Works on: unsorted AND sorted arrays.

Binary Search

Requires: a sorted array.

Algorithm: compare the target to the middle element; if less, search the left half; if greater, search the right half; repeat.

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;  // found
        } else if (arr[mid] < target) {
            left = mid + 1;  // target is in the right half
        } else {
            right = mid - 1;  // target is in the left half
        }
    }
    return -1;  // not found
}

Time complexity: O(log n) — each comparison eliminates half the remaining elements.

Example trace: search for 42 in {2, 8, 15, 27, 42, 67, 89}

Step	left	right	mid	arr[mid]	Action
1	0	6	3	27	42 > 27 → left = 4
2	4	6	5	67	42 < 67 → right = 4
3	4	4	4	42	Found! Return 4