00:00I have taken my main function and defined my target as 0.
00:05I need output index 4.
00:10I will write public and static.
00:13I will write return type int because it has to return index.
00:17I will give it search.
00:19I will pass my array and pass my target.
00:23I need starting index and ending index.
00:27How will call from main function?
00:28How will call from main function?
00:30I will pass my target in search.
00:35I will pass the starting index as 0.
00:37I will pass the ending index as array.length-1.
00:42This will give me target index.
00:46I will print this target index.
00:49Now let's complete my function.
00:52What do I have to do in the function?
00:54I have to do this.
00:55My work is to find out mid.
00:59It will be starting index plus ending index minus starting index by 2.
01:04I can also write starting plus ending by 2.
01:08But I will write this.
01:10Now I will see my different cases.
01:12This is my best case.
01:15The first case is that I got my target here.
01:19How will it get?
01:20If my array of mid value is equal to my target,
01:24then I got my index.
01:27In that case, I got my index.
01:27In binary search, I will compare it to mid.
01:29If I got the target at mid, I will return the value to mid.
01:33That the mid is my target index.
01:35If we think that this has not happened,
01:37then what will I do in that case?
01:38In that case, I will put my mid to line 1.
01:42I will see that case.
01:43I will put my mid to line 1.
01:46For that, what condition was written?
01:48How will I put it on line 1?
01:49I will put it on line 2.
01:50When my starting index is less than equal to my value of mid.
01:56In that case, my mid is on line 1.
02:00So this condition will be when I put my mid to L1.
02:03If not, there will be an else condition.
02:05When I put my mid to line 2,
02:08I will put an else condition here.
02:11If this is false, then it will be true.
02:15So here I have case A.
02:16What was the case A?
02:18Case A said that I have to search on left.
02:21What was the condition of left?
02:23The condition of left was that
02:25my starting index value is less than equal to target.
02:31And my target is less than equal to my value at ending index.
02:36Let's understand logically.
02:38Logically means that my target is greater than starting index
02:42or equal.
02:43I have no ending index here.
02:45That needs to be mid to the end.
02:46But it is small.
02:48I will explain this in the diagram.
02:50Which case is happening?
02:52This case is happening.
02:54When I put mid here.
02:56If I have to identify,
02:57I have to search in line 1.
02:59Where I have to search.
03:00When I put mid here.
03:02And my target value is greater than starting index.
03:04Or equal to it.
03:06But mid to it is small.
03:07It is equal to it.
03:08So I will put my target here, I mean I will put my left part
03:13What will I call for? I will search again
03:17I will search recursively, I will pass array and target
03:22Starting index will be starting index but ending index will be my mid value
03:27And I will return the search as my final answer
03:33Here is my first inner recursion call
03:36Now I have only left part
03:38How much is the starting index?
03:40The middle part is my left part
03:42The other is else's condition
03:44The else is my case B, which I am searching for right
03:48For the right, I will call array and target
03:52This time I have no starting index, this time I have to pass mid plus 1
03:55And what will I pass at ending index?
03:57I will pass at ending index
03:59I will pass here
04:00And since I have searched with mid
04:02I have not searched for mid
04:04I have not found my element
04:06So I can pass here mid minus 1
04:08Here I will do return
04:10Whatever value comes from search
04:12I will return
04:13I have covered my case
04:15When I have placed on mid line 1
04:16Now let's talk about line 2
04:18If I have placed on mid line 2
04:20Then what will I be placed on case C
04:21What will I be placed on case C
04:22When I have searched in right
04:24If this is my mid
04:27And this is my ending index
04:28Then my target
04:29I have placed between these two
04:31This is my right part
04:33I have placed on case C
04:34So let's write the condition
04:39If my array of mid is less than equal to my target
04:43And and my target is less than equal to my array of ending index
04:48This means target is mid
04:50And target is less than ending index
04:52So I have to search in right
04:54In this case I have to search in right
04:54I will call the search
04:58Array target
04:59In this case my starting index is mid plus 1
05:02And ending index is ending index
05:05And what will it be
05:07And what will it be
05:07It will not be
05:08I have to search in left
05:11This is my case D
05:12Here I will search in left
05:15So I will search
05:17Array target
05:19This time I will pass starting index
05:21And ending index is mid minus 1
05:23So like binary search
05:25We can say modified binary search
05:26We can say that
05:27What we have seen
05:29Before we have seen
05:30We exist in mid
05:31Then we have seen line 1
05:32Condition
05:33And then line 2
05:34Condition
05:35Now let's see the base case
05:37The base case
05:38For me
05:39If my starting index
05:41Value is greater than my ending index
05:43So I will return to this case
05:46In this case
05:46In this case
05:47In this case
05:47In this case
05:48In this case
05:48In this case
05:49In this case
05:55In this case
05:56I will return as index
05:57Because minus 1
05:58In this case
05:59In this case
06:01In this case
06:02In this case
06:02This is my search function
06:03Starting index
06:04Ending index
06:05And you will see
06:06In this case
06:07If I write recursive
06:09In this case
06:09In this case
06:10It is solved
06:11Here I have seen
06:12That my starting index
06:14Ending index
06:15So I will return to this case
06:16So I will return to this case
06:17What's the work
06:18If I start mid
06:18Is I get checks
06:20Or not
06:21Then I see
06:22What I have seen
06:22In this case
06:25Which is in this case
06:26In this case
06:27In this case
06:29So I have seen
06:29I have sent recursive calls
06:30And I have
06:32We have told them
06:32That the calls
06:33Will give me the correct answer
06:34So I have seen
06:35The recursion
06:37What I have seen
06:38In this case
06:38In this case
06:41In this case
06:41When I put line 2 on the right side,
06:44the fourth case is that I will put it in the left side.
06:47I also called here to search for search.
06:50And here I have seen that the recursive function
06:53will see itself.
06:55In the main function, I have called here
06:58and printed the target index.
07:00Let's do it save.
07:02And once we run it.
07:04My output has come to 4.
07:07If I change the target and 6,
07:09then what will happen?
07:10My output will come to 2.
07:12Because I put index 2 in this array.
07:16So we solve the search, inserted and rotated array.
07:20And this technique is not only for recursion.
07:22This whole divide and conquer
07:24we can also do with iteration.
07:25So the homework problem is that
07:27we have solved the entire problem.
07:29Now we have solved the modified binary search
07:32by recursion.
07:33We have solved the modified binary search
07:35by iteration.
07:37We have solved the problem.
07:38We have solved a single loop.
07:39We can also solve this problem.
07:41And if we are able to do that,
07:42then we will clear that
07:44binary search is also clear.
07:47And this problem is also clear.
07:49Because we have understood recursion
07:51and understood the whole logic.
07:52We have done dry run
07:53on a small array.
07:55Then we will write iterations
07:56and write iterations
07:57will be very easy.
07:58It will be very easy.
07:58So, if we are not going to do it,
07:58we will do it.
