What is Binary Search?

Binary search is a common algorithm used in programming languages and programs. It can be very useful for programmers to understand how it works.

We just released a binary search course on the freeCodeCamp.org YouTube channel. You will learn how to implement binary search in C and C++, but the concepts apply to any programming language.

Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.

The course was developed by Harsha and Animesh from MyCodeSchool. MyCodeSchool is one of the oldest software channels on YouTube. Animesh currently works as an engineer on Google's search team. Harsha was the highest ranked Indian programmer on the Top Coder competitive programming platform.

MyCodeSchool has an inspiring and sad story. You can read about it here in this article written by Quincy Larson.

Here are the topics covered in this course:

• What is Binary Search?
• Implementation and common errors
• Recursive implementation
• Finding the first or last occurrence of a number
• Count occurrences of a number in a sorted array with duplicates
• How many times is a sorted array rotated?
• Search element in a circular sorted array

Watch the full course below or on the freeCodeCamp.org YouTube channel (1.5 hour watch).

Transcript

(autogenerated)

In this lesson, we will talk about one of the most famous and fundamental algorithms in computer science binary search, we find the application of binary search in a large number of problems in a large variety of problems in computer science.

But here, let's try to learn it in its simplest form.

And to do so, we will define a problem first, the problem is given a sorted array of integers, a sorted array means that the elements in the array are arranged either in increasing order or in decreasing order like in this array, here the elements are arranged in increasing order, let's say the name of this array is a the size of this array is nine.

So we have index starting zero till eight.

Now given such an array and a number or an integer x, we want to find out whether x exists in this array or not.

And if x exists in this array, then we want to find out the position at which x exists in this array.

So for example, if x is at one does it even exist in the array? Yes, it even exists in the array and it exists at index seven, does 25 exists in the array no 25 does not exist in the array does 21 exist in the array? Yes, 21 exists in the array at position three at index three.

Now, what would be the logic to find out whether x exists in this array or not? One simplest approach can be that we can scan the whole array to find out the desired number.

So we start at index zero, and compare this element with x.

If it is equal to x, then we are done with our search we are we have found the element in the array.

If not, we go to the next element.

And we keep on comparing with the next element until either we are finished with the array, or we find the number.

So let's say if we wanted to find 63 in this array, then our search will be over when we teach index six, we start at index zero and our search will be over at index six.

If we wanted to find a 25 our search will be over at index eight with the conclusion that 25 does not exist in the array.

This approach will work irrespective of whether the array is sorted or not.

And if I have to write the code for this, it will be pretty straightforward.

Let's say I want to write a method search that takes an array A its size N and the element sorry number x to be searched for and the code would be we will run a loop starting zero till n minus one.

So for I starting zero to n minus one, if the element at index i is equal to x, then we return I which means returning the position at which we have found element x and our search will be over.

And if we cannot find any such AI then we return minus one, let's say returning minus one means that we could not find the element we could not find x in the array.

Now with this algorithm, if we are lucky, we will find x at first position itself.

So in the best case, we will make only one comparison and we will we will be able to find the result in the worst case when x would not even be present in the array we will scan the whole array we will make n comparisons with all the elements in the array and then we will be able to give back a result that hey x does not exist in the array.

So the time taken in the worst case is definitely proportional to the input size of the array, sorry, size of the array.

Or in other words, we say that this would be big O of n in terms of time complexity, it's always good to analyze the running time of an algorithm in the worst case and find out the upper bound of the time taken.

Now, in this case, the time taken grows as a linear function of n.

So, we also call this search linear search.

And once again, if we are using linear search, we are not using any property like the array sorted or not whether that is sorted or not this will work.

Now, let us try to improve this algorithm using the extra property of the array that it is sorted and I will make some space here first.

Let us say we want to find out whether 13 number 13 exists in the array.

So x is 13.

And we want to find out whether x exists in the array.

Now we will use a different approach this time instead of instead of comparing x with the first element, as we do in the case of linear search, we will compare it with the middle element in the array.

Now the size of this array is nine so the middle element will be at index four Now there can be three cases here.

case one can be that x is equal to the middle element.

If x is equal to the middle element, we have already found x in the array.

case two can be when x is less than the middle element, and case three can be that x is greater than the middle element.

Clearly, if x is equal to the middle element our search is over.

Because we have found x in the array, if x is less than the middle element, then because the array is sorted, it lies before the middle element.

And we can discard the middle elements, middle element and all the elements after middle element.

Similarly, if x is greater than the middle element, it lies after the middle elements.

So we can discard all the elements before the middle element, and of course, the middle element as well.

So in case two, and three, we discard half the elements from our search space and reduce our search space.

So in this example, when x is 13, initially, our search space is the whole array, X can exist anywhere in the array.

Now we compare it with the middle element, which is 36.

Now x is less than 36.

So it exists, it should exist somewhere before 36.

So we discard all the elements after 36 and 36, as well.

So now the problem gets redefined, we need to search x only between index zero to three.

So how do we keep track of the search space, we keep track of the search space using two indices start and end.

So initially, the start would be zero, and n would be the last element in the array, in this case, the index eight because initially the whole array is our search space.

And we calculate made as start plus n upon too.

Now once we find out our reduced search space, we adjust Start and End accordingly.

So in this case, after comparing 13 with 36, and discarding half of the array, our end now becomes index three, which is nothing but one less than the middle element.

Now we again find out the middle element in this reduced search space.

So here the middle element will be three plus zero by two, if we take only the integral part three plus zero by two would be 1.5.

And if we take the integral part the middle element will be index one once again is it equal to x? No six is not equal to 13 is x less than the middle element? Is it case two? No, it is not x is greater than the middle element.

So this time, we discard the middle element and all the elements towards its left and this time we shift start to mark our new search space.

Now, the new search space is starting at index two and ending at index three.

Now, what is the middle element three plus two is five five by two is 2.5 and the integral part is two.

So this is our middle element.

So x is not equal to middle element we have found our element.

So we are done with our search.

This kind of search where we reduce the search space into half at each comparison is called binary search.

Once again we are able to reduce the search space by two or in other words, we are able to reduce the search space into half only because the array is sorted array being sorted is a precondition for binary search.

Okay, so let us now write code for this algorithm.

I will write a method binary search that we'll take as argument and array A, its size N and a number x to be searched for in the array and I will initialize two variables start to zero and end to n minus one.

So start and end define our search space initially the whole area is the search space.

Now, I will write a condition here while start is less than or equal to and I'll come back to why I am writing this condition.

So while this is true start is less than or equal to and we will find out the middle index of the search space as start plus end upon two.

And now we will write three cases.

If the middle element is equal to x, then our search is over.

We return the index stored in the variable made and exit from the function.

If x is less than the middle element, then we need to discard all the elements having index greater than or equal made.

So our end of the search space now becomes mid minus one.

And in the third condition, which will be x greater than the middle element, which will be the default condition after these two if and else if we need to discard all the elements with index less than or equal to mid, so, our start becomes mid plus one.

And if we exit this while loop without returning anything, then we return minus one, which will mean that we were not able to find the element x in the array.

Now, why this wild statement here with a condition start less than or equal to end, what we are basically doing in our algorithm is that we are reducing our search space recursively by adjusting the start and the end pointer.

Now, there must be an exit condition to our recursion, the exit condition can be either we find the element in the array, so, we return and exit or we exhaust the whole search space when start is equal to end or start is less than E and then we still have such space, when start is equal to n then our space has only one element.

So, when this condition becomes false, we have exhausted our search space, we need to exit the loop and we need to return minus one to tell that the element the number x does not exist in the array.

Now, once again in this case in the best case, we can find the element x in just one comparison, when the first middle element itself will be the element x in the worst case, we will keep reducing the search space till the search space becomes one element.

So, from n we reduce to n by to and from n by two we reduce to n by four and we go on till our search space becomes one.

Now, how many steps does it take? Let's do some math here.

Let's say it takes k steps to reduce n to one by keep by dividing by two at each step.

So, n by two upon K will be equal to one and if you solve this, then k will be equal to log of n the base will be two.

So, in the worst case, binary search will take log n comparisons and so, the time taken also in the worst case is proportional to log in or in other words, it is big O of log n in terms of time complexity and big O of log n is a lot lot lot more efficient than o n algorithm.

So this was binary search, we will take more problems on binary search in the coming lessons.

Thanks for watching.

In the previous lesson, we learned 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 will 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 six.

So the indices are from zero to five.

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 two pointers to variables that point 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 this variable start and end or we may also call this 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 is equal to low plus high upon two or start plus end upon two and we take only the integral part.

So here five plus 0.2 would be 2.5.

And taking the integral part will give us this index two as the middle index.

So we are searching for 10 number 10.

And initially we are in a state where lower index is zero, higher index is five and so mid index is two.

Now we see that 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 six is six equal to 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 six and all the elements before six, because they are also less than 10.

And we shift start to point at index three.

So we go to this state lower index three higher index five and now we search for our number in this part of the array only.

Now if we calculate mid and mid is equal to four five plus three upon two, is it equal to the target element 10? Yes, it is equal to so we have found found our element on our search is over, we found 10 at index four.

Okay, what if we were we were searching for the number nine in the array, if we were searching for nine till this tape, it would have been the same thing.

Now at this step, the middle element is 10 we compare it with nine and I'll also modify it here now 10 is greater than nine.

So definitely nine can only exist before 10 we need to discard this part of the array and we need to go to a state where our search space is defined by low equal three and high equal to three now three is both low and high and mid element of this range would also be three only.

Now, this middle element is also not equal to our desired number nine is not equal to eight.

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 now 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 binary search that will take 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 two variables low and high and initialize them to zero and n minus one respectively low and high at at any point give us the segment within which x may lie okay.

So, now we declare another variable made that is calculated as low plus high upon two.

Now, we compare x to the element at index made and there can be three conditions here first condition will be when x is equal to the middle element the element at index made and in this case our search is over we will simply return the index made and when we return from our method we exit it now the second case can be when x is less than a made now, because x is less than the middle element it will lie before made.

So, now we redefine our segment by shifting end to shifting the higher index to mid minus one and the should be as f okay 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 are the lower index and lower index will be equal to mid plus one.

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 loop here.

Now, when do we stop executing these steps we stop either when we find elements.

So, either when we return or when we are done looking at all the elements.

So I will put a condition here while low is less than or equal to high, when low becomes greater than high then the segment defined by low and high will not be a valid segment, Melo is equal to hi then we will have only one element in the segment.

Now if we exit this while loop without returning anything, then we can say that the element x is not in the array let's say we return minus one to say that x does not exist in the array okay.

So this is the binary search method.

And and let us now write the main method and try to use this function.

In the main method, I will first declare and initialize an array let's say the name of the array is a and we fill some elements into this array in sorted order.

Remember, the array being sorted is a precondition for binary search.

Okay, so this is an array of size eight.

Now let's ask the user to enter a number that we will search in array.

So we will write a printf statement here and now let us in a take input of this number.

Now I will call binary search to search whether this Number exists in the array or not size of the res eight and we want to find out x Okay I will rather name this as x, because we have been naming the target element as x throughout okay.

So, now if index which is the return from the method binary search is not equal to minus one then we have found the element x in a.

So, at this stage we will print something like number x is at index index index is the variable name as well else we will print that we could not find x in the array.

Let us now run this program and see what happens.

So, we are asked to enter a number let's say we want to search for number 15 in the array okay.

So, this says that number 15 is at index six and let us now try to search a number that does not exist in the array let's say we want to search for 18 and output is number 18 not found there are some common errors that happen in binary search implementation resetting these indexes low and high should be done correctly and we should always be careful about this exit condition from the loop.

One more common error is when people do not put this bracket here now, what will happen here is that the precedence of division operator is more so, high by two will be calculated first and then it will be added to low so, this bracket is important we need to put this bracket here and some people also calculate mid as instead of calculating it as low plus high upon two we also calculated sometimes as low plus high minus low upon two and this is a better way of doing it because sometimes low plus high can exceed the maximum value that an integer can store.

So, like a 32 bit integer or 32 bit signed integer can store maximum value of two to the power 31.

Now, if both low and high are pretty high, then high plus low will exceed two to the power 31 and cause issues in our program execution it should be pretty evident that this expression evaluates to high plus low upon two only.

The only difference is that we are avoiding overflow by not calculating high plus low in this expression.

Okay.

So, this was binary search implementation.

And in this implementation we have used loop so we have written a an iterative implementation, you can write binary search using recursion also, I would recommend that you try that on your own.

In the coming lessons, we will see more variations of binary search and its application in other scenarios.

So thanks for watching.

In our previous lesson, we learned about binary search and we also implemented binary search, but we implemented an iterative version of binary search in which we used loop to write our program.

Now in this lesson, we will write binary search using recursion.

Let us first quickly write an iterative version of binary search.

So, I will write a method binary search that will take as argument a sorted array the size of the array n and an element x that is to be searched for, then we initialize two variables low and high low to zero and high to n minus one.

And we say that while low is less than or equal to high, calculate middle index as low plus high upon two.

It's a better practice to calculate mid as low plus high minus low upon two, which is the same thing except that we are not calculating low plus high sometimes low and high individually are within the limit of within the range of an integer variable but high plus low overflows the range or limit of an integer variable.

Now there are three conditions if x is equal to the middle element we have found x in the array so our search is over we return the index made and exit else if x is less than the mid element, we are just high to mid minus one two to say that we discard anything which is on or after made, because x is less than the middle element and that is sorted as if x is greater than a made which should be implicit here.

For the third condition.

As the third condition in this case we said low as made plus one.

And if we come out of this while loop without finding anything, we will return minus one to say that x does not exist.

In the array, what we are essentially doing here is that if we have an array in which elements are in increasing order, then we first compare x with the middle element.

And if x is equal to the middle element, it's fine.

If x is less than the middle element, it must exist before this element in this highlighted section, and if x is greater, it must exist after the middle element in this particular highlighted section.

And we keep on retied repeating this process in the new segment.

until either we find x or we cannot divide the search space any further at low equal high our search space becomes or rather reduces to size one reduces to only one element.

After that we cannot divide it any further.

Binary search is a typical example of a divide and conquer algorithm in which at each step we are dividing the problem into half.

Let us now write recursive implementation.

So once again, I will write a method binary search that will take a sorted array A and this time the arguments will change a little we will take two arguments low and high to mark the segment of the array in which x may lie at any stage x is the element to be searched for.

And the logic would be something like once again, we will calculate the mid index.

And then we will have three conditions.

If we find x, that's good, we return the index at which we have found it.

If x is less than a made, we call binary search recursively on the range low.

And I'm running short of space here.

So I'll create some space here.

And we will run the we will call binary search recursively for index low to mid minus one.

So x is now to be searched between index low to mid minus one else if x is greater than a mid, which will be the third condition anyway, we will return binary search from mid plus one to high so we make a recursive call to search eggs from index made plus one tail Hi, when we write recursion, we should always look for a base case a base condition where we would stop our recursion in this case, we will stop our recursion if we find the element.

So, this case will return an exit and we will not make any further recursive call, but what if we do not find the element what what if we do not find x in the array we have another base condition for that where we need to exit if low is greater than high then we do not have a valid segment in the array.

And in this case, we can say that we have exhausted our search space.

So we return minus one to say that x does not exist in the am short of space here.

So I'm writing these two statements in the same line.

So, these two are our base conditions that would cause the recursion to stop or exit and this condition low greater than highs the same condition which we are checking here to stop the loop.

Let us now quickly simulate this recursion using an example.

Let's say we have this array A a sorted array of size nine and we want to search for number 63 in this array.

So we make a call to the function binary search and I will write b s here a shortcut for binary search okay we pass to the function the array and lower index should be zero and higher index should be able to say that initially the number can exist anywhere in the array from index zero to eight and the number to be searched for is 63 now we go inside the function is low greater than high No.

So we go ahead and calculate mid mid would be calculated as for the element at index made index four is 36 and 63 is greater than 36.

So, we come to this else condition the third condition and we make a recursive call to search for 63 within range mid plus one would be five to eight.

Now once again for this function low greater than high is not true.

So we calculate mid mid would be six if we take only the integral part and element at index six is 63.

So we have found this element we will return made so we return six here and this method finishes and this method also returns six to its color maybe the main method.

Let us now say that we want to search for number 25 so we make this call to binary search from the main method.

Now once again we calculate the made now element at index 436 is greater than 25.

So we make a recursive call to search for 25 from index zero to three.

Okay now is low greater than high is zero greater than three no so we go ahead and calculate made Made would be one element at index one is 625 is greater than six.

So we make a recursive call to search for 25 between indices two and three, now made would be two, and this time, we will make a recursive call to find 25 in the range three to three, it's still a valid range low is not greater than high, mid would be three.

And now 25 is greater than 21.

So we make a recursive call using the third condition to mid plus one would be four and lower high would be three still, and this time low is greater than high.

So we come to this condition, where this method simply returns minus one and finishes.

Now this method also returns minus one and this gets propagated all the way up.

And finally, this method returns minus one to its color the main method while writing recursion, we must be very careful about the base conditions, like we have these two base conditions here.

If we do not get our base conditions, right, our recursion may go on endlessly causing the program's memory to overflow and causing it to crash.

The time complexity of this algorithm is big O of log n, the time taken is proportional to login.

And this comes from the fact that if we keep dividing the size of the array by two at each step, then it will take us log n steps to reach array size equal to one.

Now one obvious question which one is better the recursive implementation or recursive implementation or an iterative implementation? Well, anything that we can write using recursion, we can write it using iteration and anything we can write using iteration, we can write it using recursion, iteration is a slightly more performant.

It's better in performance, because we do not have to store all these states of all these functions, the extra functions in the memory.

But writing recursion may sometimes be very intuitive and easy to write.

For most practical reasons, you may choose any of these according to your comfort.

So that's not an issue.

Okay, so this was recursive implementation of binary search for you.

Thanks for watching.

In the previous lesson, we saw the implementation of binary search in its basic form, we solved a problem in which if we have a sorted array of integers, something like this, and if we want to find out whether a number exists in this array or not.

So let's say we want to find out whether number 10 exists in this array or not, then our algorithm returns us that 10 exists at index three.

And if we want to search for a number that does not exist in the array, then our algorithm returns us that the number that we're looking for does not exist in an array.

So if we want to search for 11 in this array, then our algorithm says that 11 does not exist in the array.

Okay, so now, I will modify this array.

Now, this array is still sorted, but the only difference is that we have three occurrences of number 10 in the array.

Now, let's say we want to search for the number 10 using binary search, then what will be the index of 10 that will return we could return to also index to also we could return index three also.

Or we could return index four also, the normal binary search implementation that we saw previously exits as soon as it finds out any occurrence of a number in the array, so there is no guarantee that we will find the first occurrence or the last occurrence.

Now in this lesson, we will see two different variations of binary search, one variation will always give us the first occurrence of a number in the array.

And another variation will always give us the last occurrence of the number that we are searching for in the array.

Okay, so let us first write the basic implementation that we had written previously.

I'll quickly write a method binary search that takes three arguments array, its size N, and the element to be searched for x.

And we will initialize two variables low and high to zero and n minus one to mark the segment of the array in which x is probable to lie.

And while low is less than or equal to high, we calculate the middle index as low plus high upon two, and then we compare x with the middle element.

And if x is equal to the middle element, then we have found exe and our search is over.

We exit from the method by returning this index made.

So we are exiting as soon as we found as soon as we find any occurrence occurrence of x, not necessarily the first or the last occurrence, but any occurrence.

If x is less than the mid element, we add just high to mid minus one to say that x will now x is now probable to lie before the mid element and the third and default condition.

When x is greater than the mid element, so, in this case we had just low to mid plus one.

And if we come out of this while loop without finding x, then we return minus one to say that we could not find x in the array.

Okay, let us see a simulation of this for this particular example simulation of this algorithm for this particular example, I will draw three columns here, low, high and mid.

And let's say the number to be searched for is 10.

So x is 10, size of the array six, So, initially low is zero, so the size of the array is seven.

So, initially low is zero high is six.

Now, we have started to execute this while loop we calculate made as low plus high upon two, so mid would be three.

Let's also drag column A made, okay, this looks better.

Now, a three is 10.

So is x equal to A made? Yes, it is.

So we return three, we return three.

And we will say that game over because we have found an injury and we return immediately we do not care that there is another 10 at index two.

Now, if we want to find out, if we wanted to find out the first occurrence of 10 in the array, we should not have said gameover we should have said that Okay, I have found 110 at index three, let me go and see towards the left, if there is another 10 at any lower index.

And if it is there, I will return that one.

So I will modify this algorithm slightly here.

At the beginning, let's say we take a variable result, and initialize it to minus one.

I'll come back to why I'm initializing it to minus one.

And I'm short of space here.

So I'm writing two statements in the same line with a comma.

Now, when the condition is that x is equal to the middle element, instead of returning and exiting the execution of the function, we modify result to x.

Sorry, we modify result to made the index at which x lies and we adjust high to mid minus one.

Once again, I'm short of space here, so I'm writing two statements in the same line.

So, these two statements will execute for this condition if x is equal to the middle element.

Now, what do I really mean here, what I mean is that if we found x in the array, then we have stored the index in the variable result at which we found x and then we modify our segment we do not stop our search and we modify our search space by adjusting high to mid minus one.

So, we keep on searching for x before this mid element.

So, if we see the simulation now, then we do not stop here we make highest two and continue our search now mid would be one a mid would be for I will also write the value of result at any state.

So far our result is so far we have found 10 at index three.

So, our result is three now for this case low zero high two and mid one we will go to the condition this one when x is greater than the middle element, so low becomes mid plus one so low becomes too high is already too now made would also be to a mid would be 10 Now we come to this condition, we again came to x equal to the middle element of the segment.

So we now modify result to the new index at which will have found x so results will be now two and high becomes mid minus one which will be one low is two now this condition lower less than or equal to high fails.

So we exit y loop here okay there should be one more modification to my code, I will return result here okay.

So, we are seeing here that found 10 at index two.

So, this way, we have found the first occurrence of the element 10 in the array we are returning result here once we complete the while loop and we are not returning result inside the loop, the result is initially minus one.

So if we do not find any x it is never modified.

And we return minus one to say that we could not find x in the array.

And if we find any x in the array and I'll quote put braces here to mark that these two statements execute for this if condition, we stored that index in this variable kind of saying that so far, this is the leftmost result that I have.

And then we go on searching towards the left by left a means towards the lower indexes.

So we modify high to mid minus one if we find another x, then this x is left of the previous index.

So we discard the previous result and modify our result okay.

So, this is binary search to find out the occurrence of first element in the array.

If we want to find out the last occurrence in the array, then there will be only a slight modification to this code.

When we find x we do not stop the search like we are doing here.

And we go on searching towards the right towards the higher indices by modifying our window window or the segment or the search space by adjusting lower to mid plus one by adjusting lower index to mid plus one And this is the only change that we need to do to find out last occurrence in the array okay.

So, let us quickly see simulation for this implementation also.

So, once again we start with low zero high six and we also start with the result minus one minus one means that we have not found x in the array so far now made would be three and the mid element would be 10 we are executing the while loop here, now, we come to this condition x is equal to a mid So, first we modify our result we found an x at index three and then we modify low to mid plus one which would be four.

So, earlier our window was the whole array.

Now, our vendor spaces this and we already have information about the right most 10 that has occurred so far Okay, so, now mid would be five a mid would be 18 now, we go to this condition x is less than a made so, now high becomes mid minus one So, we have this range our window or search space is now this and so far we have found 110 at index three now mid would be five plus four upon two and if we take only integral part then it is for a mid would be 10.

So, once again we come to the come to the condition when x is equal to image so we modify the result to the new index four and we modify lower to mid plus one So, low becomes five high becomes five.

So, far the highest index of 10 that we have found is four and our search window is now only index five.

So, mid would also be five and a mid would be 18.

Now 80 is greater than 10.

So, we will again once again go to this particular condition.

So low is still five and high becomes four now.

Now this is not a valid search space, this is not a valid segment low less than or equal to high condition fails, so we will exit the loop, exit the while loop and our game is over we deserve we return whatever we have in the result.

So we will kind of say that found 10 at index four.

So this is binary search to find out the last occurrence of an element in the array in a sorted array.

The time complexity of this algorithm is big O of log n.

Or in other words, we can say that the time taken is kind of proportional to log of n.

In the coming lessons, we will see more variations of binary search, we will see other scenarios in which binary search is applied.

So thanks for watching.

In this lesson, we will solve a very famous programming interview question.

And the question is that, given a sorted list of integers, we want to find out how many times a particular element occurs in this list.

So let's say we are given a list in the form of an array.

Here we have an array of size 12.

And the elements are in increasing order.

Now how many times does number five occur in this array, five occurs five times and how many times does number two occur in this array, two does not occur in the array.

So we will be given any such sorted array and a number x.

And we have to find out how many times this number x exists in this array.

Now we want to solve this problem programmatically.

So let us think through the different approaches that we may want to follow.

The simplest approach is that we can scan the whole array and count the occurrences of x in the array.

So if I have to write a function find count that will take as arguments array, its size N, and the element x to be searched for the element x for which we want to find out the count.

So the logic would be pretty straightforward, we will take a variable initially, let's say the name of the variable is count and we initialize it to zero.

And then we run a loop starting zero till n minus one.

And if a I or the element at index i is equal to the element x, we increment count.

So count becomes count plus one and finally when we count come out of this loop, we return count.

So we are performing a linear search where we are scanning the whole array to search for element x.

We could optimize this algorithm a little bit, something like this, because the array is sorted once we reach a stage, when AI becomes greater than x, we can stop counting.

But still in the worst case, this loop will run n times.

When all the elements in the array are same then This loop will run n times.

So in the worst case, this algorithm, the running time of this algorithm is proportional to n.

In other words, the time complexity is big O of n.

This is a very simple solution for this problem.

And if you give this solution in a programming interview, the interviewer would be like, I do not like this, give me something better.

So, how do we find out a better solution? Whenever in a problem, we are given a sorted data or a sorted collection, we should try to think about applying one very famous algorithm that makes the best use of this property that data is sorted.

And this algorithm is binary search.

So, can we make use of binary search in this problem, one thing that we can do is that using binary search, we can find out any occurrence of the number x in the array.

So, let's say in this example, we want to find out count of number five.

So we let's say we find out using binary search in big O of log n time, that number five exists at index six.

Now, because the array is sorted, all occurrences of five will be adjusting to this.

So, we can go towards higher indices starting this index, and look for all the five and then we can go towards the lower indices, and look for all occurrences of five.

But once again, if the whole array is number five, only, all elements being same still is a sorted array, then we will scan all the elements, we will access all the elements in the array, and eventually the time complexity will be big O of n, only the time taken will be proportional to N only in the worst case.

So, using binary search kind of does not give us much advantage if we use binary search in its basic form, big O of n because to perform binary search, we will take big O of log n time.

And then to find out all the adjacent occurrences of x, we will take big O of n in the worst case.

So, for higher values of n, log n is negligible in comparison to.

And so this is eventually big O of n, we are not writing writing pseudocode for this approach, we'll leave that as an exercise for you.

With these two approaches, we are still big O of n in the worst case.

So what do we do? Well, if you remember from our previous lessons on binary search, we can write a binary search to find out the first occurrence of an element in an array.

And similarly, we can write a variation of binary search to find out the last occurrence of an element in an array.

And this forms the basis of our third approach.

And I'll clear some of this and make some space.

Okay, so we can use one variant of binary search to find out the first occurrence of an element in an array.

And we can use another variation of binary search to find out the last occurrence.

And if we know the last and the first index at which the element occurs, then we also know the count of it in the array.

So once again, we will write a method find count that will take an array its size N and element x.

And let's say we find the first occurrence of the element in the array using a method find first, which is a variation of binary search.

And we will use another method called to another variant of binary search, that will give us the last occurrence of the element in the array, then we can return count as last index minus first index plus one.

And I'm not handling the case here when the element is not present in the array.

Let's say we will handle it well in our actual implementation.

Okay, so the first method call if we are using binary search will work in big O of log n and the second method call to find out the last occurrence will also work in big O of login.

So overall, the time complexity to find out the count of an element in the array would be big O of log n.

And that's really great.

We have described how to find out the first or last occurrence of an element in a sorted array using binary search.

We had written pseudocode for the algorithm in our previous lesson and there is a link to the previous lesson in the description of this lesson.

But let us now go and write some real code.

To solve this problem.

I will write a C program.

Let us first write a simple normal binary search and then we will modify it to find the first or the last occurrence.

Let's say we have a method binary search that gives me the index of element x in the array.

in binary search we first define two indices low and high, two variables low and high initially set to zero and n minus one, respectively.

And then we find the mid element and as low plus the mid index as low plus high upon two, and then we compare the middle element with the number x.

And if we, if middle element is equal to x, we have found our element.

So we simply return the index mid else, if x is less than the middle element because the array is sorted, remember array being sorted is a precondition of binary search, we set high as mid minus one kind of saying that search in the segment left to the middle element.

And if x is greater than the middle element, we adjust lower to mid plus one.

And we keep repeating this process again and again till the time we have a valid segment and a valid segment is till the time low is less than or equal to high.

And if we come out of this loop without finding anything, then we return minus one to say that x does not exist in the array.

problem with this implementation is that as soon as we find any x, we return.

So there is no guarantee that we will find the first index or the last index, if there are duplicates in the duplicates of x in the array.

So what we do is we will, what we will do is we will modify the algorithm slightly, we will have another variable, initialize it to minus one.

And now when we find x, then we do not return an exit, we update the result variable to kind of say that, okay, this is the lowest index of x so far, and then we continue the search.

So if we want to find out the first occurrence, then we adjust high to mid minus one.

So we update result and go on searching towards lower indices lower segment.

And finally, if when we come out of this loop, then we return result.

So if we do not find anything, any occurrence of x, we simply return minus one, because this was initialized to minus one.

Now this implementation will give us the first occurrence of x in the array.

And what if we wanted the last occurrence, the only difference would be that we will go on searching towards the right or higher indices, so we will say that low is equal to eight plus one now go on searching towards the higher indices.

Now I want two different functions for finding out the first or the last occurrence.

But if you see there is difference in only one line in these two implementations.

So what I'll do is I'll use the same function to retrieve both first and the last index based upon another argument of flag.

So let's say we have a flag as a Boolean parameter.

Search First, if it is true, we want to search for the first occurrence and if it is false, then we want to search for the last occurrence.

So if we want to search for the first occurrence, then we want to, in the case, when a mid is equal to x, we want to adjust high to mid minus one else we want to adjust low to mid plus one.

Okay, let us know write the main method.

What I'll do is I'll first initialize an array.

And I'll ask the user to input a number x.

Now we want to find out the count of x.

So we will first make a call to binary search method to find out the first index in the array.

So we will pass the array, the number of elements in the array, which is 12.

And we will also calculate the number of elements using this particular equation size of a upon size of a zero size of the number of bytes in the whole array upon the number of bytes in each in teaser in each element.

And we want to search for x and we'll pass true because in our method declaration, if this flag is passed as true, then we search for the first index, else we search for the last index.

Now if first index is returned as minus one, then the element is not in the array.

So no need to find the last index, we can simply print that the count is zero.

Else, we find out the last index and this time we make the call to the same function binary search with only difference that this time we will pass the flag as false.

So we will say that, hey, give me the last index.

And we will print count as last index minus first index plus one.

So this is our code.

This is our method binary search.

And we have made call to binary search twice to find out the first and the last index and we decide first or last index using this flag.

Let us now run this code and see what happens.

Let's say we want to find out the count of number three, then this gives us that three occurs twice which is right.

Let's now try number five and count of five is five.

And let's give x is equal to two two is not present in the array so the count will be zero.

So this is an optimized algorithm to find out Count of an element in a sorted array.

This is a classic implementation of binary search.

In the coming lessons, we will see more problems on binary search.

So thanks for watching.

In this lesson, we will solve another programming interview question.

And the question is that we are given a sorted array that has been rotated.

So let's say we have been given a sorted array with these elements, the size of the array is six, so we have indices from zero to five.

And let's say we want to rotate this array anti clockwise rotate this array towards the right.

So, each element will shift by one towards the right except the last element which will shift to the first position in the array and the resulting array would be this and this is rotated once and if we rotate the array twice, the resulting array would be this and this is of course, rotated twice.

And such an array is often also called circularly sorted array.

So we have been given such a circularly sorted array and there is one more condition there are no duplicates in the array, all the elements in the array are distinct.

So given such an array, we have to find out how many times the array has been rotated.

So how do we solve this problem? One thing that should be pretty evident is that if we know the first element or the minimum element of the sorted sequence in the array, then we know how many times the array has been rotated.

And when we say the number of times 30 has been rotated, for this problem, we mean rotation in anti clockwise direction or rotation towards the right, the number of rotations of the array would be the number of elements before the smallest element or the minimum element in the array.

So in this case, there is only one element before two which is the minimum.

So clearly this array is rotated once here we have two elements before the minimum element.

So this is rotated twice.

In fact, if we see then the number of rotations is equal to the index of the minimum element.

So our problem is basically finding out the minimum element in the array, the index of the minimum element in the array.

And we are done.

We know that how many times the array has been rotated.

So how do we find out the index of the minimum element, the simplest approach would be to scan the whole array perform what we also call linear search.

And the pseudocode will be something like we will have two variables, one to store the minimum element and another to store the minimum index.

Let's say Initially, the first element is the minimum element and then we run a loop from one till n minus one where n is the size of the array.

And if the element at if index is less than the minimum, we update the minimum and the minimum index.

And finally, when we come out of this loop, we will have the index of the minimum element Clearly, the running time of this algorithm would be big O of n the running time will be proportional to n.

Now, this will give us the correct answer, this is a correct solution.

But in this solution, we did not make use of the property of the array that it is circularly sorted, can we use this property of the array and improve this algorithm improve the time complexity of this algorithm? Well, let us see.

Now, we will make use of the property that array is circularly sorted, and we will use a variation or modification of binary search algorithm to solve this problem.

Now, what do we do in a normal binary search algorithm? Let's say we have a sorted array like this, we first find out the middle element in the index in the array.

And then we see whether this is the element we are looking for or not.

If it is not the element that we are looking for, we either go searching towards the left, or we go searching towards the right based upon whether the element that we're looking for is greater than or less than the middle element.

So at each step, we divide the problem into searching something in half the array.

at each step, we discard half of the elements, we discard half of the search space, and we keep on going until we find the element.

Now in a circularly sorted list like this, our problem is to find out the first element of the sorted sequence.

This particular element is kind of the pivot or the junction in the circularly sorted array.

So now we will use a variation of binary search to find out this pivot element which is also the minimum element in the array.

What we essentially do in a binary search Is redefine a search space or segment within which our desired element is probable to live by two variables low and high, the lower index and the higher index and at each step, we either find an element or we reduce the search space by half by discarding half of the elements in the segment and creating a new segment.

And now, we look at the new segment we kind of divide the problem at each step into half.

Now, in this problem for each segment, we will look at couple of things, there can be a case when the lower the element at lower index is less than or equal to the element at higher index.

Now, this will be possible only if the segment is already sorted, if the segment is already sorted the minimum element in the segment and that's what we are finding out the minimum element in the array and if we can find out the minimum element in the segment that will be the minimum element in the array as well.

So, we will return simply return the index low because the array is already sorted.

So, the element at lower index is the minimum if the segment is not sorted, we calculate the middle index.

And now, we try to see if our middle index is the pivot or not.

Now, how do we find out the pivot if you see there is a special property of the pivot or the minimum element in the array if we see the next and the previous elements of the pivot element in a circular manner.

So, if it is the last element, the next element will be the first element, then for the pivot element both next and previous element in the array are greater than it like here 18 and five are both greater than two.

No other elements in the array will have this property except the pivot element.

Let's define this property as pivot property.

So, here we calculate next as MIT plus one modulo n modulo n because if mid is the last index in the array, we need to go to the first element.

So, modular operation does that and previous would be mid minus one modulo n and we will also add n here so, that mid minus one does not become a negative number.

So, our case too is that a made is less than or equal to a next and it's also less than and equal to less than or equal to the previous element in the circular array in the circularly sorted array.

If this is the case, once again we have the pivot or the minimum element in the array.

So, we will return the index made.

So, far in these two cases, we have found our element straight off and we have not felt the need to divide the array divide the search space segment.

If the middle element is not the pivot, then can we use a property where we can say that we can discard the right half or we can discard the left half and we can go to one of the halves to search for the pivot element.

Well, yes, it is possible to do so, if the middle element the element at mid index is less than or equal to the highest element at high index high then the segment starting the mid index and extending right towards till the high index, this whole segment is sorted and the pivot cannot exist in the right segment.

So, in this case, we will say that we need to search for the pivot in the left half.

So, we will adjust high to mid minus one and case four would be when the mid element is greater than or equal to the element at lowest index.

Now, in this case, it is not possible that the pivot is in the left.

So, we will go and search in the right so, we will adjust lower to mid plus one.

So, we keep reducing our segments at each step and try to find out the answer.

Now, let us simulate this approach this algorithm for this particular example.

So, for this example, case one obviously is not true initially.

So, we find out the middle index.

Now, the pivot property is not true for the middle index.

So, we look at case three, when we look at case three we basically are looking whether this whole part of the sequences sorted or not including 18 and the whole elements towards the right.

So, 18 is not less than or equal to eight.

Now, we look look for case four.

And when we look for case four, we mean to check whether this complete sequence is sorted or not.

Well, this is sorted.

In fact, if the array is not sorted, then one of these two sequences will always be sorted.

You can pick up some of examples, some examples and try to see and this is what forms the basis of our divide and conquer approach.

This is what forms the forms the basis upon which we discard half of the elements.

So now we need to adjust low to mid plus one.

So we have discarded these elements from our search space are not new search spaces starting at two.

Now this array is sorted.

case one is true for this segment, sorry, this segment is sorted.

So we simply return the index of two which is 0123, and four, so, we return four here and our searches over now, we have found the pivot element.

So, we know that the array is rotated four times equal to the index of the pivot element of things about this algorithm, this algorithm will work only if there are no duplicates in the array.

And that was our initial condition also in the problem, if there are duplicates this reduction of search space into half is not possible.

And let us now write code for this algorithm and see whether it works or not.

So, I will write a method find rotation count, that will give me how many times a circularly sorted array A is rotated, and is the number of elements in the array.

So, we first define low and high.

And then while our search space is valid, we first see whether the segment is already sorted.

If it is sorted, we return the lower index.

So, this is our case one else we calculate mid as low plus high upon two and then we also calculate the next and previous have met.

And if made satisfies the pivot property we return made.

Else if the middle element is less than or equal to the higher element, then we discard the right half, and we adjust higher index to mid minus one else, if a made is greater than or equal to a low, then we discard the first half the left half.

If the array is not sorted, one of these two conditions will always be true.

And only one of these conditions will be true, not the both of them.

Let's say if we are not able to return anything, if we are not able to return anything within the while loop, then we return minus one it will be minus one will be returned only for an invalid scenario when maybe the array is not circularly sorted, its properties are not true.

Now, in the main method, I have initialized an array of size 11.

And I have called this function find rotation count.

And I'm trying to print the count.

Let us see what happens if I run the program.

This says that the array is rotated six times, which seems to be correct.

Let's now modify this array.

Let's run this for a test case when the elements are already sorted.

Okay, this also looks fine.

So we are good.

Now I have used four cases to solve this problem.

There are a couple of different other implementation approaches as well, the underlying idea would be the same to use binary search.

But we can implement using some different conditions.

I encourage you to try them out on your own, or quickly Google search for code snippets.

So this was one interesting problem using solve using binary search in the coming lessons, we will see more such interesting problems.

Thanks for watching.

lesson we will solve yet another very famous programming interview question.

And the question is that we are given a circularly sorted array, which means that a sorted array has been rotated.

And in the previous lesson, we had also solved a problem where we wanted to find out the number of rotations in a circularly sorted array.

This is an example of a circularly sorted array, the first element in the sorted sequence is at index four, and then we go towards the right.

And then after the last element, we go to the first element.

So this is the start of the sorted sequence.

And this is the end of the sorted sequence.

Each element in the sorted sequence has been shifted four positions ahead, the array is rotated four times in anti clockwise direction or towards the right.

Now given such an array, we have to find out whether a number x exists in this array or not.

So how do we solve this problem? The simplest approach would be to perform a linear search, where we scan the whole array to look for x.

But in this approach, we will not make use of the property of the array that it is circularly sorted.

And the time complexity for this approach would be big O of n, where n is the number of elements in the array.

So what else can we do? Whenever we have a sorted data, and we have to search for something, we should always think about binary search ads as one of the possible approaches.

Binary search as we know executes in big O of n log n.

At most, we make log n comparisons to find out our element in the array.

And big O of log n is the best time complexity to have for a solution.

So let's see if we can apply binary search in some form.

To solve this problem, let us pick up this circularly sorted array, the example that we have in the left and now we will use a variation of binary search to find out an element x in the array like we do in the normal binary search, we will first define two indices low and high initially to the first and the last element in the array respectively.

And then we find out the mid element as low plus high upon to the mid index.

So far the logic is the same.

Now, the first case would be that the element at mid index a made is equal to x.

As we do in a normal binary search, we will compare the middle element with the number that we are looking for x and if this is equal to x, our search is over we will return made telling that x exists at index mid, if a mid is not equal to x, then if the array was a normal sorted array, then we would have either gone to the left half or the right half depending upon whether x is greater than or less than the middle element.

But we cannot apply this straightforward logic to discard one of the half's in this case, but there is a property that we can explore it and discard half of the elements.

If you see then, the elements in the array are always increasing except only at this particular point, which is the junction point or the pivot point, where we have the first element or the minimum element in the sorted sequence.

Now, if we pick any segment or any sub array, then if it does not contain this pivot point, if it does not contain these two elements, which form the boundary, the break point, then all the elements in this segment will be sorted.

And if the segment contains these two elements that form the breaking point, then the segment will not be sorted.

Now, the mid element divides the segment into two halves and this breakpoint or the pivot point will lie only in one of these halves.

So, at least one of these halves will always be sorted, we will make use of this property and we will discard half of the array at half of the search space at each iteration of the binary search.

So, our case two will be if a made is less than or equal to a high basically we are looking at this particular part of the array, we include the mid element and look for the segment extending till the highest element.

If this condition is true, then this whole segment is sorted.

In this example, this segment is not sorted.

But if the segment was sorted, the right segment was sorted, then there would be two conditions let's say these conditions are to a and to B, we know that x is not equal to A made but if x is greater than a made and x is less than or equal to a high then it definitely lies in this sorted half.

So, we adjust lower to mid plus one to say that go ahead and search in the right half as if it is not so, we will have a condition when we will say go go search in the left half in the unsorted half okay this will be the case when the right half of the array sorted case three would be when a low or the first element in the sequence is less than or equal to the middle element less than or equal to a mid.

Now in this case, we are looking whether this particular segment starting low index all the way till mid index is sorted or not.

Now, once again we will have to condition to conditions when we know that this half is sorted, it is very easy to verify whether x is probable to lie within this segment or not within this sub segment or not here if x is greater than or equal to a low and x is less than a made x cannot be equal to the mid element because then we will not reach the case three then x is probable to lie in the left half for this condition.

So in this condition, we will adjust high to mid minus one else we will search in the unsorted half by adjusting low to mid plus one.

So this is our divide and conquer strategy for binary search.

Let us now write code for this And see if it works, I will write a function circular array search that will search for a number x in an array of size n, and it will return the index of x if it is found in the array.

So like we do in a normal binary search, we will first define two variables low to zero and high to n minus one.

And while low is less than or equal to high, while our search space is valid, while our segment is valid, a valid segment segment will have at least one element when low will be equal to high, we calculate the mid index as low plus high upon two.

Now, if x is equal to the middle element, then we have found x we return the index mid ELLs, we need to decide whether to go in the left half or the right half, whether to go searching towards the higher indices or the lower indices.

And we do so by first finding out which part of the array is which part of the search space is sorted.

If a made is less than or equal to a high, the element at index high, then the right half is sorted.

the right half is sorted, then we can easily check whether x is probable to live within this sorted half or not.

So if x is greater than the middle element, and x is less than or equal to the element at index high, we go searching to the right sorted half by adjusting low to mid plus one.

Else, we know that the element is not in the right half, so it is definitely in the left half.

So we will adjust high to mid minus one to go to the left half.

Now, right half is sorted for sure we know that but left half, it could either be sorted or unsorted, it doesn't matter.

For some special case, when the segment itself is sorted, the left half could also be sorted.

But irrespective of that, using these two conditions, we are discarding one of the halves and we are going to one of the we're choosing one of the sub segments.

Okay, so now if the right half is not sorted, then the left half definitely will be sorted.

So either we write this condition A made greater than or equal to a low.

Or maybe I should write a low less than or equal to emit as we had written previously.

So this is case three, even if we do not write this condition and simply write an else we are fine because this will be true anyway, at this point.

So now the left half is sorted.

So we can see whether our x is probable to lie in left half.

Now if if x is between a low and a mid less than or equal to greater than or equal to a low and less than a mid, then it's probable to lie in this half.

So we will adjust high to mid minus one.

Else if x is not probable to lie in the left half, then we go searching towards the right by adjusting low to mid plus one.

And finally, if we come out of this while loop without finding x, without returning anything, we return minus one to say that we could not find x in the array.

Let us now write the main method, we will first initialize an array and this is the same array.

The elements are the same as we have used in our examples throughout.

Now let's ask the user to input a number x from the console.

And now we call the method to search for x, the size of the array is eight.

So we pass eight as the second argument.

Now if this method returns minus one, we will say that we could not find the element in the array, the number in the array.

And if it is not minus one, we print the index.

So this is our C program.

And now let's run this and see what happens.

Let's search for the number eight in the array.

And this seems to be correct.

The element eight is at index six.

Let's run this again and search for number 12 in the array.

And this also is correct.

And this seems to be working for other cases as well.

And let's modify this array.

Let's say we want to pick up an array in which the elements are already sorted.

Let's pick up eight elements again.

Let's search for element four in this array, okay, this is also fine.

So we seem to be good for all test cases.

Well actually no we are not good for all test cases.

If we have an array with duplicates, like this, this array is still circularly sorted.

This is the first element in the sorted sequence zero.

But if we have duplicates in the circularly sorted array, it will not be possible to decide whether left half is sorted or right half is sorted.

Using the conditions above that we have used using these this condition.

So the array has to be strictly increasing in a circular manner, and all the elements need to be distinct.

If we run this, let's say we want to search for a number zero, then this is zero not found in the array which is not correct.

If there are duplicates, we cannot do any better than big O of n, we will have to perform linear search only if the elements are distinct, we can perform binary search.

Okay, so this was searching an element in a circularly sorted array with no duplicates using binary search.

Thanks for watching.