Guided Project: Searching Algorithms

Linear Search

Example Implementation

                        public static int linearSearch(int[] array, int target) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            return i;
        }
    }
    return -1;
}
                    

Time & Space Complexity:

Time Complexity: O(n) - In the worst case, we need to check every element
Space Complexity: O(1) - Uses a constant amount of space regardless of input size

Example Usage:

int[] numbers = {5, 12, 8, 130, 44};

System.out.println(linearSearch(numbers, 12)); // 1
System.out.println(linearSearch(numbers, 10)); // -1

Binary Search

Example Implementation

                        public static int binarySearch(int[] sortedArray, int target) {
    int left = 0;
    int right = sortedArray.length - 1;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (sortedArray[middle] == target) {
            return middle;
        }
        if (sortedArray[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return -1;
}
                    

Time & Space Complexity:

Time Complexity: O(log n) - We eliminate half of the remaining elements at each step
Space Complexity: O(1) - Uses a constant amount of space regardless of input size

Example Usage:

int[] sortedNumbers = {1, 5, 8, 12, 20, 45, 67, 99};

System.out.println(binarySearch(sortedNumbers, 12)); // 3
System.out.println(binarySearch(sortedNumbers, 10)); // -1

Recursive Binary Search

Example Implementation

                        public static int recursiveBinarySearch(int[] sortedArray, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    int middle = (left + right) / 2;
    if (sortedArray[middle] == target) {
        return middle;
    }
    if (sortedArray[middle] > target) {
        return recursiveBinarySearch(sortedArray, target, left, middle - 1);
    }
    return recursiveBinarySearch(sortedArray, target, middle + 1, right);
}
                    

Time & Space Complexity:

Time Complexity: O(log n) - Same as iterative binary search
Space Complexity: O(log n) - Due to the recursive call stack

Example Usage:

int[] sortedNumbers = {1, 5, 8, 12, 20, 45, 67, 99};

System.out.println(recursiveBinarySearch(sortedNumbers, 12, 0, sortedNumbers.length - 1)); // 3
System.out.println(recursiveBinarySearch(sortedNumbers, 10, 0, sortedNumbers.length - 1)); // -1

Practice Challenges

Challenge 1: Find First and Last Position

Given a sorted array of integers and a target value, find the starting and ending position of the target value.

                        // Challenge: Find First and Last Position
public static int[] searchRange(int[] nums, int target) {
    // Your code here
    return new int[] {-1, -1};
}
                    

Example:

int[] result1 = searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8); // Output: [3, 4]
int[] result2 = searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6); // Output: [-1, -1]

Additional Resources:

If you want more practice with search algorithms, check out these LeetCode problems: