Binary Search – Iterative Implementation and common errors


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

Leave a Reply

Your email address will not be published. Required fields are marked *