Binary search

Best Case: 1

Average Case: logn

Worst Case: logn

Binary search divides the array in half and checks to see if the element being search is eaither higher or lower than the mid point. It keeps halfing until the element is found or not without having to check each element in the array.

The following example implements a small function that searches for a value and returns it if found.

C++/C example

   
//Binary search function, simply returns the location of the element if found.
int BinarySearch(int A[], int left, int right, int x) {
    //Checks if they have overlapped, if they have the array has been searched through
    if (right >= left)
    {
        int mid = left + (right - left) / 2;

        //If the element is found at the middle point print its location.
        if (A[mid] == x)
        {
            return mid;
        }
        //If the element being searched is smaller than the middle point it will be on the left of the array
        if (A[mid] > x)
        {
            return BinarySearch(A, left, mid - 1, x);
        }
        return BinarySearch(A, mid + 1, right, x);
    }
    //If the element is not found it will return -1
    return -1;
}

int main() {

int A[] = {0, 2, 5, 6, 7, 8, 9, 10, 11, 12};
int x = 9;
int size = sizeof(A)/sizeof(A[0]);

int location = BinarySearch(A, 0, size - 1, x);

if (location == -1) {
    std::cout << "Element not found" << std::endl;
} else {
    std::cout << "Element found at: " << location << std::endl;
}

return 0;
}

                

Summary

This is a better method for searching through a sorted array because it doesn't matter where the element is in the array as it won't affect its time complexity by much. The only benefit linear would have if the element happens to be at the start of the array therefore taking no time to find it, unlike binary where it would have to go through the whole process.