Logout

Linear and Binary Search

Linear Search

This is a straigh-forward way to look for an certain "key" value in an array by looking at one element at a time, in order, until it is found (or not found).

If, while doing the search the key is found, the element where it is located is immediately returned, and the search stops. This is nice in that it doesn't waste time continuing to loop through the array once the key is found.

If the key is not found, -1 is returned. So the code making use of this method would have an if/else block checking to see if the returned value was -1, and if so, that means the key was not found; whereas if a number other than -1 is returned, that is the element where the key value is to be found.

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

Example array of integers. (Note that it does not need to be sorted for the linear search to work.)

[0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]
22   88   45   89   102  48   17   2    50

So if we were looking for the key value 45, we would look in element 0 - is it there? No. So we would look in element 1 - is it there? No. And so we would continue looking to element 3 - is it there? Yes. So at that point we return the key.

Whereas if we were looking for a value which is not in the array, such as 55, we would look in the 0th, the 1st, the 2nd element and so on, but never get to the point where arr[i]==key, so the for loop would end after i got up to the length of the array, and the last line of the method would execute, which is to return -1.

 

Binary Search

The binary search is a much more efficient way of searching than the linear search. In the binary search we reduce the possible number of elements which might contain the key by a half with each loop. So the maximum number of times we will have to loop looking for a key is log N, with N the number of elements. For example, we could locate a key value in an array of 1,000,000 in 20 steps (log 1,000,000 is 20).

The basic idea is that if we have an array of a certain size, and the values are ordered from least to greatest, if we pick the middle element and that is not what we are looking for, and we compare that value to the one we are looking for, we can eliminate the necessity of seraching half of the array. You see if the value we are looking for is greater than that middle value, we know that we don't have to worry about looking through the first half. In which case we take the second half, pick the middle element of that, and repeat the process of disregarding the half than cannot contain the key value due to it being greater or less than the middle value.

This is the "Non-recursive" or "Iterative" Binary Search. You'll note that there are two ways of looping: 1. iteration - the normal way, with for or while loops -, and 2. recursive, a more sophisticated way of achieving looping. We will look at a recursive binary search later on.

Remember that in order for this to work, the array needs to be sorted.

public int binarySearch(int arr[], int key){
    int low =0;
    int high = arr.length -1;
    while(low <= high){               // Keep on looking for the key until the low and the high cross each other - if that does happen, it means the key was not found.
        int mid = (low + high) / 2;
        if(arr[mid] == key)
            return mid;               // This is what will happen if/when we find the key in the array.
        else if(arr[mid] < key)
            low = mid + 1;            // since the arr[mid] value is less than the key, we can eliminate looking at the left side of the remaining elements
        else
            high = mid -1;            // i.e. the arr[mid] value is greater than what we are looking for, so we can eliminate looking at the right side of the remaining elements
    }
    return -1;
}
  A classic video explaining the binary search.