Searching

In this case, the problem we are trying to solve with search is: given an element N - find that element in a sorted array. The only algorithm worth mentioning here is the binary search.

Binary Search

• Runtime: O(log N)
• Recommended reading

As we know that the array is sorted, we can use a divide and conquer approach. Here we will repeatedly divide the array by using the middle point as a pivot. If the element we are after is smaller than this pivot, we will look only to the left-hand side of the array, and start this process all over again.

By doing this we would reduce the runtime to O(log N), rather than doing a linear search - which would take O(N).

Here is the code in Java:

Recursive approach

int binarySearch(int[] array, int n, int low, int high) {
    if (low > high) return -1;

    int middle = (low + high) / 2;
    int pivot = array[middle];

    if (pivot < n) return binarySearch(array, n, middle + 1, high); // need to go right
    else if (pivot > n) return binarySearch(array, n, low, middle - 1); // need to go left
    else return pivot;
}

Iterative approach

int binarySearchIterative(int[] array, int n) {
    int low = 0;
    int high = array.length - 1;
    int mid, pivot;

    while (low <= high) {
        mid = (low + high) / 2;
        pivot = array[mid];

        if (pivot < n) low = mid + 1;
        else if (pivot > n) high = mid - 1;
        else return pivot;
    }

    return -1; // Error
}