Binary search. checking for the existance of an element in O(logn)

Suppose we have an array of length N. All the elements are sorted in an ascending order. We have also another number M and we want to find that number in our array. We can use a simple linear search buy just looping from the first element to the last one and check if we can find the number M or no. This algorithm has a complexity N. An average computer can do 10^8 actions in one second so if our N=10^11 we will wait for 1000 seconds until we get our result.

    If we use binary search for the same purpose we will have to wait log(1000) seconds which is nothing compared to 1000. The binary search algorithm suggests to divide the array into half every step. We declare to variables showing from where to where we are searching. To make it more clear initially we have 2 variables P and Q. P will show the left border while Q will show the right border. Initially P=1 and Q=N; now we take the middle element which has an index of (P+Q)/2.  We compare that middle element to our element M. If we get as a result that M is grater than the middle element we don’t need to search on the first half anymore. So we update the value of P and make it the middle index and we do the same actions for the new updated P and Q until P equals to Q or, P and  Q are different only by 1. Lest do it on an example.

We need to check if the number 5 exist in our set of elements or no.

Note

We will determine “the first half” as the first half  of the elements between P and Q and the “second half” as the second half of the elements between P and Q.

Step 1

Index	1	2	3	4	5	6	7	8	9
Elements	1	4	7	12	20	23	27	35	104
Position of P and Q	P								Q

Now we take the middle element which is (1+9)/2 = 5

The 5^th element is 20 . Now we can say that 20 is grater than 5. Note that the elements are sorted in ascending order which means that we don’t need the second half any more.  We just found out that our element is not on the first half in only one step. We update the value of Q giving it a value of (P+Q)/2 .

Step 2

Index	1	2	3	4	5	6	7	8	9
Elements	1	4	7	12	20	23	27	35	104
Position of P and Q	P				Q

Now we again need to check the middle element between P and Q which is the third element. The third element is 7. 7 is greater than 5 so we don’t need the second half again. We update the value of Q giving it a value of (P+Q)/2 .

Step 3

Index	1	2	3	4	5	6	7	8	9
Elements	1	4	7	12	20	23	27	35	104
Position of P and Q	P		Q

And again the same way. We take the middle element and compare to 5. Now its less than 5 so this time we don’t need the first half. We update the value of P .

Step 4

Index	1	2	3	4	5	6	7	8	9
Elements	1	4	7	12	20	23	27	35	104
Position of P and Q		P	Q

Now we can see that there are no more numbers between P and Q. So we can say for sure that there is no element which is equal to 5.

IF YOU HAVE ANY QUESTIONS LEAVE THEM IN COMMENTS> NO QUESTION WILL BE UNANSWERED