Data Structure and Algorithms

Goal:
At the end of this article you should be able to:
understand and be able to implement both linear and binary search algorithms using both recursive and iterative version,
understand the time complexity associated with each of them and the differences between them.

We're going to implement our first algorithm on search method called Binary Search method; and in fact if you're at this level am sure you've already written your first algorithm, you might not realize it but you've.

Scenario:
//declaring and assigning an array

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

Question:
Find me the index of number 5 from the given array, arr above?
As human being, you might start from the either end, left or right and sequential moving to retrieve number 5 while keeping track of index. You’re doing an algorithm called Linear Algorithm.

You can achieve the same Algorithm using loops; and I’m going to use for loop for this demo.
Let’s create a method call linearSearch below

public static int linearSearch(int[] list, int value) {
        /*
         * takes int array and int value
         * return the index of the value if found 
         * otherwise -1 indicating not found
         */

    //declare current element

    int currEl;

    for (int i = 0; i < list.length; i++) {
        // Assigning current element
        currEl = list[i];
        //checking whether we found value to return its      index 
        if(currEl == value) return i;

    }
    /*
     * after searched through the entire array, list         * return not found index, -1
     */
    return -1;
     }  
}

That was linearSearch method. We started searching from the left of the array and sequentially looking for each element in the array to check whether it’s the value we’re looking for, if it’s we return its index otherwise is not found in the array after we’ve checked all the element in the array, so we return -1 indicating that is not found.

Analyzing the algorithm complexity associated with this method

Quiz:
let N = the number of steps needed
Remember arr is the variable of our array above

How many N steps will it take us to find the first element, 1 in the array, arr? 1 steps, you got it!
This is what we called best case scenario
no matter the length of an array, it will always take us one step to find the first element in an array
In Big Ohh notation its O(1), constant time operation
How many N steps will it take us to find an element which does not exist in an array, arr? 10 steps, Correct!
Because we’ve to search the entire array, arr which will took us arr.length (10) times before returning not found, -1
How many N steps will be needed if an elements that does not exist in arr, if arr increases to N numbers of elements? N steps, Brilliant
In Big Ohh notation, it’s represented as O(N), linear time complexity

Better way to Search an element in an array!

We can do better search, in fact an algorithm called Binary Search.
Binary search algorithm reduces the problem by halve in very look up!
You don’t get that, that’s cool, I don’t too. Just kidding, However do me a favor, smile! Great let’s continue.

Let’s bring down our array above

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

At first when I asked you to find me the index of element 5 from the array, arr you started from one end maybe left and was going sequentially to find the index of element 5. That approach was great but expensive compared to this, binary search approach aka divide and conquer algorithm.
This time I want you to start your search from the middle, that’s Math.floor(arr.length / 2) I’m using Math.floor(float) to round down the value in case of floating figure; and don’t worry if you’re assigning arr.length / 2 to an int variable that would implicitly round it down for you. e.g int mid = (arr.length / 2);

While the mid = 5; arr[mid] = 6 and we’re looking for the element 5, NOTE: the mid is the index.

Our first look up give us element 6 while we’re looking for an element 5, then what do we do?
Straight in our mind, we should know that element 5 can never be found from the mid index and above because they're all greater than element 5; Hence element 5 must be at some index below the mid index. This is interesting, let’s throw unnecessary right halve of the array. This is our sliced array below.

 arr = {1, 2, 3, 4, 5};

repeating the same step; mid = (arr.length / 2); arr[mid] = 3
comparing element 3 with element 5, we know that element 5 is greater than element 3 hence it cannot be found from any index at mid and below. So let’s discard all elements form mid and below

 arr = {4, 5};

repeating the same approach; mid = (arr.length / 2); arr[mid] = 5
comparing arr[mid] which is element 5 with the element 5 we’re looking for, they’re the same so we should return the mid. Ahhh smile, you’ve found it and return your mid; However we ran into a bug called the index bug, not actually; Notice, this return index 1 because that’s where element 5 was found in the recent array, arr. Whereas in the original/first array element 5 is at index 4, that is the correct index and that’s what we wanted to return. This approach is completely find if we’re just checking the existence of an element in an array; return true if found else false; but since we care about the index of the element we’re looking for, we should take tract of our indexes. That would required us two more variables, let’s call them low and high for mapping our low and high indexes respectively.

Here’s the code of the concept we explained so far. Note this code below doesn’t care about the index.
The function will return true if element found, false otherwise.
I’m going to implement it recursively and I would like you to implement it using loop.

Takeaway: You only get it by doing and not by watching. Concepts matters but practical defeat theories.

public static boolean binarySearch_recursive(int[] arr, int find) {
    if(arr.length < 1) return false; 
    // for an empty array we're done
    int mid = arr.length / 2; // our mid index
    if(arr[mid] == find) return true;
    else if(arr.length == 1) return arr[mid] == find;
    else {
        if(arr[mid] < find) { // ignore the left halve
        arr = Arrays.copyOfRange(arr, mid + 1, arr.length); 
            return binarySearch_recursive(arr, find);
        }

        // ignore the right halve
        arr = Arrays.copyOfRange(arr, 0, mid);
        // slicing an array
        return binarySearch_recursive(arr, find);
      }

}

We’ve done a lot, I will encourage you take a break here at least 7 minutes and when you come back we’ll explore binary search that count indexes.

Welcome back!
Hopefully you’ve implemented your loop version of the above code, if you don’t I encourage you to go back and try it. Don’t just be reading, read and practice! If you tried and still don’t get it don’t hesitate to Google. In fact while writing this article I Googled “slicing an array in java” and stackoverflow.com was helpful.

Enough talk, let’s code!

This time around, I’m going to implement binary search method that return index of an element if found or -1 if not found. I’m going to use the loop version and you’re encourage to implement the recursive version of it.

public static int binarySearchIteratively(int[] a, int key) {
    int high = a.length;
    int low = 0;    
    int mid = (high + low) / 2;
    while (low <= high) {
        if(key == a[mid]) return mid;
        else if(a[mid] < key) {
            // search right
            low = mid + 1;
            mid = (high + low) / 2;
        }else {// search left
            high = mid – 1;
            mid = (high + low) / 2;
        }
    }
    return -1;
}

Brief explanation about the code
We assigned:
high to be the length of the array
low to be the at index 0
mid = (low + high) / 2 note because mid is an int variable there’s implicit floor division that safe us from using Math.floor(float)

while loop will continue as long as low <= high and that’s very important.
Inside while loop, we update low, high and mid depending on which portion to be search after comparing our key with a[mid].

Run Time Complexity:

We have already explained this above or if you could observe the code, for every iteration we’re reducing the problem by halve meaning we throw away the unnecessary portion. I.e for the first iteration the problem is now N / 2, second iteration N / 4 or (N/2)/2 and so on.
This in asymptotic notation aka Big Ohh is O(logN) , Logarithms complexity.

Good to know:
Do you know that first binary search was published in 1946; and the first bug-free one was published in 1962.
There was a bug in Java’s Arrays.binarySearch() and was discovered in 2006.

Linear Search vs Binary Search!
We know that Binary Search is a faster algorithm in term of time complexity however they can only be use on sorted array. That brought us to another topics, sorting algorithms, we’ll get there where we’ll implement quick sort, merge sort, selection sort, bubble sort and stupid/buggo sort.

This is it for part 1 of our Data Structure and Algorithm walk through.

You can Check out Part two here

Author Fabala Dibbasey
at Twitter
at LinkedIn