Searching : Linear, Binary and their Applications

In this article, I will try to explain how linear search and binary search works, their implementations, and also, how powerful tool binary search can be, if used correctly!

Pre-Requisites: Arrays, Time Complexity (Big-O-Rule)

Linear Search

Lets say you want to search for an element (x) in a given array (arr). The first and foremost algorithm that would strike a person is to iterate through each element of the array and check whether it is equal to the search element(x) or not.
This algorithm is called Linear Search, cause you are linearly searching for an element. The worst case complexity for the search would be O(N) , as it may happen that the element is not found, or the element is the last element.

Linear Search function code

Now lets assume that our given array is sorted i.e. the elements are given in an increasing order. If we use linear search here, again, the complexity would be O(N) but we are unable to use the fact that our elements are sorted.

Binary Search

In the above case, when the elements are sorted, we failed to use the fact and end with same complexity using linear search. In such a case, binary search comes to our rescue. Binary Search exploits the fact that the elements are in increasing order.

In linear search, in each comparison we see that, we eliminate only one element if that element is not the one required, but using a small observation, that, if we are looking at element arr[i] of the array and arr[i] > x (our search element), then it means that for all j > i , arr[j] > x , and looking at such jth indices is useless (and therefore be skipped). This is what binary search does.

Before I start explaining the algorithm, I will explain a few terms which will be dealt with often in the read.
Search Space (SS): The set of elements which are still candidate to be answers, or the set of elements where our can still lie.
Target Value/Search Element (X): The element or value we are searching for.

We have a sorted array, ARR, and we are looking for X in it. Currently our search space is the whole of ARR.

Lets define two pointers left and right, with left = 1 and right = N, assuming 1-based indexing, and,therefore SS = [left,right].

Now we start with our middle element of the search space everytime, so, we have, mid = (left+right)/2.

If arr[mid] > X, this means our SS should now become [left,mid], because the right half isn’t useful anymore. Therfore, we have reduced half the size of our search space using only one comparison.

Now in the next iteration, right = mid, left would remain same, and,
mid = (left+right)/2 again.

We keep doing this, until our search space is reduced to only one element or we find our element as arr[mid], and we check whether that is our required answer or not. Once left > right, this means, our search space has no element left in it, and hence we can quit.

Binary Search Function

Time Complexity: With each comparison (iteration), we are reducing our search space by half, therefore after k iterations, search space will be of size N/pow(2,k). So, worst case would be when we would be left with only one element, and at that time, k = logN, that is, the complexity of binary search. As compared to O(N), O(logN) much faster. Therefore, this is the power of binary search, but the drawback here is the array given has to be sorted or needs to be sorted. Few known sorting algorithms take O(NlogN) time, and hence for Q queries with binary search, time taken will be
O(NlogN + QlogN), NlogN time for sorting and logN time for each of Q queries, where as with linear search it will be O(N) time for each query, there O(Q*N) linear search, hence it is evident that, for large values of N binary search is much better.

Binary Search: Main Theorem and Applications

There is a common theorem or trick behind identifying when can you use binary search to solve a problem, that is, how binary search can be used apart from identifying an element in a sorted array.

Formal Definition: Lets say you have predicate P, binary search can be used if (and only if) for all x in SS (search space), P(x) implies P(y) for all y > x.

Informally, it means to say that you can use binary search, when you can make a statement using an element X in search space, such that if that statement is true or false for X, then correspondingly it should be true or false for Y, for all Y > X.

Example 1: Finding Square Root of a number (N)

Lets identify our search space here. Our search space here is all numbers between 0 to N.

Now, I define a predicate P(x), i.e. x*x > N . It can be observed that, if P(x) is true, this means, P(y) will also be true, for all y > x.

Therefore we can start with left = 0 and right = N, and end when our search space is quite small. But how do we define small here? Because our search space consists of all real numbers between 0 and N.

Therefore, we need to define upto what precision do I need the answer to be, and in general a precision of 10^-7 works well, hence you can stop when
R-L ≤ 10^-7 .

Function to implement Square Root

Example 2: Aggressive Cows [SPOJ]

The key point to note in this problem is that, if you can place cows with distance X, this implies you can place them all distances ≤ X also.

Here, for every distance X, it takes O(N) time to know whether distance X is possible or not, and we need to check for only logN such distances using our binary search instead of linear search.

Recommend user to code this problem by themselves before reading ahead.

Recommended Problems: [In order of difficulty level]

1. HACKRNDM [SPOJ] Very Easy
2. NOTATRI [SPOJ] Easy
3. ABCDEF [SPOJ] Medium
4. SUBSUMS [SPOJ] Medium
5. Vanya and Lanterns [CodeForces] Application of Binary Search
6. Worms [CodeForces] Application of Binary Search

There are many more problems available, but these are a few which if done along with examples will help develop good intuition of applications of binary search.

Bonus : Binary Search using STL

There are a few functions, defined within the STL, which can be used directly instead of writing binary search implementation by the user itself, though it is not recommened to use them for the recommended problems mentioned above, else where in contests, it should be used, once the reader is confident enough of how they work.

Assume a sorted array “arr” of size n, and we are looking for “value” in the array or its bounds.

1. binary_search( arr, arr+n, value); //boolean function
   It returns true or false, according to presence of value in arr.
   Note: arr should be sorted and then passed.
2. lower_bound(arr, arr+n, value)- arr;
   It returns the index of the first occurence of “value” in the array, if present, else it returns the index of the just next higher number in the array, if “value” isn’t present.
3. upper_bound(arr,arr+n,value)-arr;
   Left upto reader to explore.
4. equal_range(arr,arr+n,value);
   Left upto reader to explore.

Also, these functions can be used along with vectors instead of arrays, but I again leave it upto the reader to explore them.

Hope you liked and understood the read!