Binary Search Intro

Let’s start with dissecting the word Binary Search. Whenever the word binary comes, you will come across base 2 terms, and search means searching. In simple words, if I say it is dividing the search space into half each time based on conditions.

Let’s understand this with an example. Suppose I have given you a very big dictionary. Now I want you to search some random word, say “gamesu.” So, by brute force, you can simply go page by page and search for the word, which is, in programming terms, called Linear Search. Also, you can debate that you can randomly open any page and get the word, but if I ask you, will everyone be that lucky?

No, right? So, let’s discuss our more efficient and optimized solution, that is, binary search. Let’s go back to our previous example case. Here, we can go to half the page of the dictionary and check if the word is there or not. If not, check according to alphabetical order and go on with the left or right half, making the search space half on the basis of alphabetical order, and you eventually find the word. Well, you can ask me, how is it efficient?

Let’s discuss how it is efficient. Suppose my dictionary has N pages. Then, for Linear Search, it will take O(N) time for reading pages in the worst case if my word is at the last of the dictionary. Now, let’s check for our Binary Search. In binary search, we will make the search space half each time and will end up with one page at last where we will find our word. So, I can say

T(n) = T(n/2) + 1, and T(1) = 1.

Now, how is it going if you follow n → n/2 → n/2² … → n/2^k,

where we divided the search space k times. Now, if at n/2^k we find the word, the search space is 1. So, n/2^k = 1 ⇒ k = log₂(n), which is far lesser than N in our linear search. So, time complexity is O(log n).

Now, is this technique always applicable? No, it is only applicable if there is monotonicity. If the function is monotonic, i.e., strictly increasing or decreasing, then you can apply this. Well, if you are even a little aware of Binary Search, you will think of a sorted array and ask, how even the word “function” came? If I tell you that the sorted array can also be expressed as a function—amazing idea, right?

Suppose I give you a function:

y = x² + 7x + 6

defined in x ∈ [0, 1000]. Now, if I ask you to find the value of x where y = 264,704, can I apply binary search here? Yes, as in this range, the function is monotonic. At first, the search space is 1000. We find the mid value, that is, 500, check the value of y, i.e., 253,506. As it is less than our target y, we will check in the range [500, 1000]. Now the mid value is 750. We can check the value: y = 567,756, which is greater than our target y. New search range: [500, 750]. If you go on like this, trimming down the search space to half each time, you will eventually reach x = 511, which is our answer.

Now, we can realize values of a sorted array as y and indexes of values as x of a function, where we don’t know the function definition, but this function exists. So, applying binary search on a function is a bigger subset than on a sorted array.

I want you to find the value of x where y = 87.64, for the function I have given. Till then, bye, tkinter.