Hello and welcome to the first course for our interviewing questions in C plus plus. Today we're going to do a very simple band research question. But in addition to that I will make it like a real interview which is something different than when you are practicing in that code. So first we have a problem description given an array of integer numbers which is sorted in ascending order and an integral target, write a function to search. Target in numbers. So in interviews you will often get like a one sentence. Very simple question and then you have to ask clarifying question questions too. No, like the specific details. So for this example it is clear that the input is an array of integer numbers and sorted but we don't know the output. So we can ask what will be the output. And for this question if the target exists, we want to return its index. Otherwise we're gonna return negative ones. So -1. Here is another extreme case. You're gonna clarify about with your interviewer and there's there will be another additional constraint. So we want a algorithm with old log and runtime complexity. Otherwise it will just be a linear search but we don't want that. So the old log in runtime complexity here will be a hint to use band research, especially here the array is ordered. What banner research does is each time we're gonna compare the midpoint with our target and we decided to go left or right and bana research usually or can only be used for sorted arrays. But of course if you got unsorted array you can sort the array and then to use binary search. So here we're gonna use the plus plus and we will need some um some kind of stuff here. I want to include the leverage to make it compatible and we need to construct our own main function in our examples. So here I got to cases so let me write down in word that what these two examples is gonna be in an interview. Either the interviewer will give you some example or you're gonna come up with some. So let's go over the first example For here the target is nine. And another important thing is to clarify whether the index starts from zero or one. In this case we're going to start from zero. So for this target line is gonna be 01234. So the index of the target is four. And for the second example we got target too But there's no tool in this theory so we just returned -1. I hope this is straightforward. And let's right. The actual function to solve this problem. So let's do the function signature first. It's gonna be output and indicator for the index and we can let's call it search, we have our input. Not here I use a reference of the factor which will save us some time to avoid the copying well with plastic input and better research. It's actually very simple structure. You can just remember the structure and depends on the question. You're gonna modify the structure slightly. So for research we will have two pointers. The last printer pointing to the beginning and a red printer. Thanks to there are 22 way you can do it. So first we can let it point to the one past the end of the searching space which means that this right is not in our searching space. We will get to that later which makes this like a left closed because right is in the searching sprays and right open, right. It's not in the searching space. Later. I will show you another way which is left and right. Both both closed interval and how you modify that. And the main part of a better research is we will have a well look comparing the left and right because here the word is not in the searching space. So we always want left to be smaller than right and each time inside the globe we will have the mid printer just like said middle of the searching space. one important thing we always do here um to do this right minus left over to us to avoid any teacher overflow. So when the left and right are both very big integers we don't want to add right and left first Then divided by two. We want to get it's different and then divided by two. You will notice when you are doing little code and this is one of the extreme case. And then we got some check ins to do to see which side of the meat. We want to go first. Very straightforward is we want to check as our target is actually the same as the meat points to. If this is the case, we can just return mate, else we have other tracking. So we checked if the target is smaller than what made points to, this means we're going to continue search on the left. So we add our red pointer to recasts writers out of the searching space. So we want it to equal to meat because meat is not the target, meat is bigger than the target. And then else we want to update left pointer because we want to searching in the right after this word to be one plus mate. Because as we already said, meat is not the target. So meat is out. And then lastly, what will we return? This is very important. So let's go through this. If we find the target, We would have returned the meat here on line 28. Otherwise what we miss the target when going out of the wild look. No, because every time we just exclude the part that cannot have the target. So when we are going out of the wild That it means the target is not there. So we just returned -1. Risk that No 1 to be nowhere to be fun. So um yeah, we got this menu function, let's try this out. So let's build our function. Okay. We've got the secret key here and we build 60 PP. Uh huh. Okay, me too. And compile this thing. Okay. So it will be in a art. So here I got this, press it up but we can easily check that our function is working correctly. So in an interview, if you can compel it, you're gonna run through different examples if not you're gonna draw So you're gonna go over your function and check just line by land. Check what's your example numbers that's going to lead you to. And sometimes you need more examples than just two. But here we already cover in normal case and extreme case. So let's move on. As I said, there's another way to do research which is the left and very tired. Post closed closed interval. So let's do a search to I'm just going to coffee over the search function and every name is search too. Let's do some modifications 1st. The right. We wanted to be within a certain interval. I do the sides -1 here. In simple as fast because side is one because the Vectors starting from zero. The site actually went past the principal. So right now, right is searching space in the world of we wanna actually changing the smaller than two smaller or equal to because left and right can be the same. And if they're the same, we're still in the searching space. And then the mid calculation is the same. The target equals checking is the same. And when the target is smaller than meat, We search on the left and right is made -1 and then the else is the same for the return is still the same. So yeah, we just finished our second way of binary search. Um I recommend remembering this structure and later on we can do some more complex questions to see how we use this structure to tackle. Um More difficult questions. Yes. So that's it. Thank you forward. Of course.