2.1 - Search Algorithms.md

Search Algorithms

Sequential Search

Algorithm

int sequentialSearch(int[] arr, int k) {
    for (int i = 0; i < arr.length; i++) {
        if (k == arr[i]) {
            return i;
        }
    }
    return -1;
}

Time Complexity: O(n)

Binary Search

Important Points

• Requires the search array to be ordered.
• Uses the divide & conquer approach.

Algorithm

int binarySearch(int[] arr, int k) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] < k) {
            low = mid + 1;
        } else if (a[mid] > k) {
            high = mid - 1;
        } else {
            return mid;
        }
    }

    return -1;
}

int binarySearchRecursive(int[] arr, int k, int low, int high) {
    if (low > high) return -1;

    int mid = (low + high) / 2;
    if (arr[mid] < k) {
        return binarySearchRecursive(arr, k, mid + 1, high);
    } else if (arr[mid] > k) {
        return binarySearchRecursive(arr, k, low, mid - 1);
    } else {
        return mid;
    }
}

Time Complexity: O(log n)