RecursiveBinarySearch - 雙語字幕
So, in this video, we will be looking at a binary search recursive function.
Now when I say binary search, it is basically a method of searching for an element in the array.
So, let's say the number that I have or an array.
elements that I have in the array are 12, 3, 5, 10, 6 and 7, right.
Now the prerequisites that you require for performing a binary search operation on any array is that your array needs to be sorted.
Now the example that I have given is for searching in an array which has the elements in ascending order.
So, the prereq for this binary search function is that the elements of the array need to
be sorted in ascending order and when I say ascending that means smaller to bigger.
So, if I have to sort this array.
I would say 3 as the first element,
then I would say 5, then would say 6, then I would say 7, then I would say 10, and I would say 12.
And if I look at the indexes of these elements, it goes like this, right?
So, if you notice here, the number of the elements that I
have, Now, what you basically do in a binary search function is that you first find the mid which
is going to be the index of the middlemost element and you put it as the first index
plus the last index divided by the So,
for this array, my first index is 0 and my last index is 5, which will always be n minus 1.
So, if you do a integer division, the result that you get is 2, right, 5 divided by 2 is 2.
And what you do,
the element that you are searching for,
which I have named as target in my index So,
if then will So, let's assume the target for this particular search I have is 10.
This is my target.
And you compare now the target with the element at the index made, which is my 6.
So, if your element is bigger, then the element at made, you would limit your search to the
second half of theory, that means this portion.
However, However, if the element had been 5, I would limit my search to the first half of the array which is this one.
How do you do that?
You will simply say, I will take you back to the code.
You will say if your target is more than A mid and you do notice on line number 92,
I'm saying my mid is equal to 1st plus last divided by 2.
Right?
So I'm limiting my search in the entire array when the function is called for the first time.
So my mid is evaluated as 2 in this situation and I will come to the base case.
So, if you notice, my target is not equal to A mid, because my A mid is 6, right?
and my target is 10.
Had it been equal I would just say return that particular location which will eventually happen in this case but not for right now.
Is my target more than aim it?
Yes.
So how would you limit your search to the second half?
Look at the arguments that I have in the function call.
I have the array.
My first becomes made a plus 1.
If you notice the second argument on line 90 is first.
That means from where do you want to begin your searching?
And I put it as made plus 1.
So in this case my made was 2 and now I am saying I'm calling the function.
So the first call for the binary search happened with a.
My first was 0.
My last was n.
1 minus 1 which is 5 and the target element was 10.
Since time I have found out the middle is equal to 2 and my target is more than a 2 I would limit my search to the second
half that means I would make index 3 as my starting point and of the array.
That means I will recursively call the function with the same array,
but the starting as mid plus one,
which will be three, the last remains the same and the target remains the same, which is in this case, right?
If you notice line number 98, please mid plus one is plugged into first, last is plugged into last and target is plugged into target.
So now the mid will be reworked,
that means my mid will again be first plus last by 2i,
again now find out the middle position or the middle location in this array.
Now it is going to be,
so I cancel this out, this time it will be 3 plus 5 divided by 2 which will be 4.
So I go back to the code and if you notice,
I My first is not more than last,
but if my target is equal to A mid,
which is the situation here,
it is equal to A mid,
I would simply say return mid,
that means the value returned by the function is going to be 4, which is the index of the element.
However, if I go back to the main, if you're I am displaying location plus 1.
Location is the variable in which the return value is coming which is 4.
So the index is 4 but the location if you see is 5.
That's how I am trying to explain it.
Now let's try executing this code for an element which is not present in the array.
And I am trying to look for a number which is going to be equal to 2.
So let's see how this is going to happen.
So initially my My research is called for the array.
My first is a 0.
My last is 5 and the target is 2.
I don't have the number 2 if you notice.
So the middle will be calculated as,
so in this case,
my middle will be calculated as 0 plus 5 divided by 2, which is equal to 2, which is this particular element.
Since my target is not equal to the element at this, I will limit my search to the either side.
How do you do that?
Now time, my target is less than the value at mid.
So if I go back to the code, if you notice line number 98, please, I'm saying if target is more than amen.
case.
So it goes to line 99 is my target less than A m a day.
Yes.
So I would say binary search a comma zero.
That means my first remains the same but my last becomes a mid-minus one.
So I limit my search here.
That is the reason.
I'm saying binary search a comma made minus 1 comma target.
So 0 is my first made minus 1 which will be 1 in this case will go into last and target is this so
that means I am now calling it for binary search A is my array,
the first remains the same, but the last reduce is to mid minus 1, which be 1, and now the target is 2 only, right?
We again evaluate mid as equal to 0 plus 1 divided by 2, so which is equal to 0, right?
And are talking about integer division, just pay attention to that.
This 0.
Now target is 2.
Is target.
So let's go back to the code.
Is my target equal to A mid line number 95?
No.
Line is my target bigger than A mid.
My A mid is A 0 which is 3.
No.
Is my target less than A midline number 99?
Yes.
So I limit my search to A and a zero again mid minus one because we go to the first half of the targeted array.
So now I would call this for the binary search.
First half so my array remains My first remains the same,
but my last becomes a minus 1, which will be negative 1, and the target is going to be 2 only.
So if you notice, your first has become bigger than the last, which is my base case.
So when I again re-execute,
after the mid is evaluated, 0 minus 1 divided by 2, which will be 0, it first says is my first more than last, yes.
Because first is still 0, but last has been evaluated as negative 1.
So this will only happen in situations when the element is not present in the array.
And that's my base case, in which case I return minus 1.
So if you go back to the main function,
if the returned values minus 1, I simply say the element is not present in the array.
So let's look at the working of this code here, it has already been compiled.
and I'm just trying to execute it, I put 5 elements.
The elements are,
so one thing before I take you to the execution,
you do look at a sort function here which I'm using to sort the elements in a sending order,
but don't bother about that,
we will be getting into searchings and sortings later on in the course,
okay, so you don't bother about that the only thing you have to look at as the binary search function Because I just did not want to create an array in the sorted manner itself.
So I want to sort that Alright,
so the elements are 12 or 7 or 3 6 and 10 So if you notice the numbers in the area at the
They are sorted in ascending order as 3, 6, 7, 10 and 12.
Now I'm trying to search for a number.
So if you notice, I'm going to put 7.
And it does say it is at location 3, I re-execute it, I 4 elements this time and I say 2, 7, 1 9.
This time I try to give a number which is not present and it does say it is not present in the array.
So that will be all for this particular video.
Hopefully this has given you enough understanding on recursive functions and happy working on your discussions and assignments.
Again, feel free to reach out if you face any issues.
That will be all.
Thank you.
解鎖更多功能
安裝 Trancy 擴展，可以解鎖更多功能，包括AI字幕、AI單詞釋義、AI語法分析、AI口語等
兼容主流視頻平台
Trancy 不僅提供對 YouTube、Netflix、Udemy、Disney+、TED、edX、Kehan、Coursera 等平台的雙語字幕支持，還能實現對普通網頁的 AI 劃詞/劃句翻譯、全文沉浸翻譯等功能，真正的語言學習全能助手。
支持全平臺瀏覽器
Trancy 支持全平臺使用，包括iOS Safari瀏覽器擴展
多種觀影模式
支持劇場、閱讀、混合等多種觀影模式，全方位雙語體驗
多種練習模式
支持句子精聽、口語測評、選擇填空、默寫等多種練習方式
AI 視頻總結
使用 OpenAI 對視頻總結，快速視頻概要，掌握關鍵內容
AI 字幕
只需3-5分鐘，即可生成 YouTube AI 字幕，精準且快速
AI 單詞釋義
輕點字幕中的單詞，即可查詢釋義，並有AI釋義賦能
AI 語法分析
對句子進行語法分析，快速理解句子含義，掌握難點語法
更多網頁功能
Trancy 支持視頻雙語字幕同時，還可提供網頁的單詞翻譯和全文翻譯功能