What are the known algorithms for searching for an element in an array?

Linear Search (Sequential Search). Checks each element of the array in order until it finds the desired one or reaches the end of the array. Simple to implement but inefficient for large arrays. Complexity: O(n).

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

Binary Search. Used only for sorted arrays. Divides the array in half, compares the target with the middle element, and continues the search in the half where the element should be. Complexity: O(log n).

// Binary Search (for sorted array)
public int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Avoid overflow

        if (arr[mid] == target) {
            return mid; // Element found, return index
        } else if (arr[mid] < target) {
            low = mid + 1; // Search in the right half
        } else {
            high = mid - 1; // Search in the left half
        }
    }
    return -1; // Element not found
}

Interpolation Search. An improved version of binary search for uniformly distributed data. Uses an interpolation formula to determine a more accurate position of the next element to check. Average complexity: O(log log n), worst case: O(n).

// Interpolation Search (for uniformly distributed sorted array)
public int interpolationSearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high && target >= arr[low] && target <= arr[high]) {
        if (low == high) {
            if (arr[low] == target) return low;
            return -1;
        }

        // Interpolation formula
        int pos = low + (((high - low) / (arr[high] - arr[low])) * (target - arr[low]));

        if (arr[pos] == target) {
            return pos; // Element found
        } else if (arr[pos] < target) {
            low = pos + 1; // Search in the upper part
        } else {
            high = pos - 1; // Search in the lower part
        }
    }
    return -1; // Element not found
}