In the previous lesson, We learnt

about binary search as an efficient algorithm to find or search element in a sorted data, in

a sorted collection. In this lesson, in some real code we will

see how to implement binary search and we’ll also see what are the common

errors that happen while implementing binary search, but

before that a quick recap. Let’s say we have a sorted

array of integers something like this, the elements are arranged

in increasing order and the size of the array is 6 so the indices

are from 0 to 5. Now let us say we want to find out whether

the number 10 exists in this array or not, programmatically

using binary search. Now in binary search what we do is, we

take 2 pointers, 2 variables that points

to, that initially point to the first and

the last element in the array. We may call them start and end pointers, we may call these variables start and end or

we may also call these low and high to mark the lower index and the

higher index. Now start and end, these two variables at any stage in our algorithm give us

the range in which the element can, the element may exist. So this, at the start of the algorithm, the

element may exist anywhere within the array.So that’s why start

and end are pointing to the first and the last

element. Now we calculate middle point using the equation middle= (low + high) upon 2 or (start+end) upon 2 and we take only the

integral part. So here (5 + 0) / 2 would be 2.5 and

taking the integral part will give us this index 2 as the middle index. So we are

searching for the 10 and initially we are in a

state where lower index is 0, higher index is 5 and so mid index is 2. Now we see that with the element at the

middle index is the desired element, if it is the desired element our search is

over. So the element at the middle index is 6 is 6=10? No, it is not. Now

we see whether this element is greater than the target

element or less than the target element. Now six

is less than the target element, which is 10, so we discard 6 and all the elements before 6 because

they are also less than 10, and we shift start to point at index 3. So we go to this state, lower index 3 and

higher index 5 and now we search for our number in this

part of the array only. Now if we calculate mid then mid is

equal to 4, (5+3)/2. Is it equal to the target

element 10? Yes it is equal to. So we have found, found our element and our search is over.

We found 10 at index 4. Ok, what if we were, we were

searching for the number nine in the array if we were searching for 9 till this

tape, it would have been the same thing, now

at this tape, the middle element is 10, compare it with 9 and I’ll also modify it here, now 10 is

greater than 9 so definitely 9 can only exist before

10, we need to discard this part of array and we need to go to a

state where our search space is defined by low=3

and high=3 now 3 is both low and high and mid

element of this range would also be 3 only. Now this mid element is also not

equal to our desired number 9, is not equal to

it. Now once we have only one element in

our search space and we have still not found our desired element our search is over, and we could not find the element. Let us know in the implement binary search and

I will write a C program now. Okay so what I will do here is I will first write

a method named BinarySearch() that will take and an integer array. Its

size let’s say the size of the array is n and let’s say the element to be searched

for is X and this method returns an integer which will be the L, index

of X. If it is found in the array. Now we will

declare 2 variables. low and high and initialize them to 0 && n-1 respectively. low and high at, at any point give us the segment

within which X may lie. Ok so now we declare

another variable mid that is calculated as (low + high) upon 2. Now we compare X to element at index mid and there can

be 3 conditions here. First condition will be even X is equal

to the middle element, the element at index

mid and in this case our search is over, we will

simply return the index mid and when we return from a method we

exit it. Now the second case can be when X is less than the mid, now because X is less than the middle

element, it will lie before mid. So now we redefine our segment by

shifting end, to shifting the higher index to mid-1 and this should be else if, ok and the third and the last

condition which will be the default condition here when X will be greater than the middle

element in this case we will redefine the segment by adjusting the start or lower index, and lower index will

be=mid+1. Now we need to keep repeating these

three steps again and again so how do we do that? so we will definitely need a loop, so we

will put a while look here. Now when do we stop executing

these steps? we stop either when we find the element or

either when we return or when we are done looking at all the

elements so I will put the condition here while ( low