1 00:00:02,230 --> 00:00:03,940 Hey, guys, what's up? 2 00:00:04,420 --> 00:00:09,520 So in the last we do, I explained to you the concept of binary search. 3 00:00:09,820 --> 00:00:13,540 Now in this video, we will see the code for binary search. 4 00:00:14,140 --> 00:00:16,420 So the Cornford business, which is very simple. 5 00:00:16,810 --> 00:00:17,530 What do I do? 6 00:00:17,740 --> 00:00:24,490 First of all, I will take two variables and start, which is initially zero and end and which is N 7 00:00:24,520 --> 00:00:25,210 minus one. 8 00:00:25,690 --> 00:00:25,920 OK. 9 00:00:26,260 --> 00:00:31,900 So if you remember, if I have an error, so start was at the first start, was pointing towards the 10 00:00:31,900 --> 00:00:32,590 first index. 11 00:00:33,130 --> 00:00:36,160 And this end was added last. 12 00:00:37,000 --> 00:00:37,310 OK. 13 00:00:37,600 --> 00:00:40,050 So how many times find the middle and compare. 14 00:00:40,390 --> 00:00:41,490 So I don't lose. 15 00:00:41,520 --> 00:00:46,060 Vital start is less than ordered close to end. 16 00:00:46,600 --> 00:00:52,130 So in the last we do, we have seen an example that if my start becomes good then. 17 00:00:52,240 --> 00:00:55,730 And then I can see that the key not found. 18 00:00:56,810 --> 00:00:57,100 OK. 19 00:00:57,300 --> 00:00:58,860 Kinnard found f start. 20 00:00:58,890 --> 00:00:59,270 Good then. 21 00:00:59,380 --> 00:01:03,550 And so I am doing the same Wildstar this less than close to end. 22 00:01:03,610 --> 00:01:05,500 What I will do I will find mid. 23 00:01:06,000 --> 00:01:09,390 So Medek was start plus. 24 00:01:09,790 --> 00:01:13,220 And by two now I will get married. 25 00:01:13,300 --> 00:01:14,860 And now there are three cases. 26 00:01:15,280 --> 00:01:16,390 So case number one. 27 00:01:17,260 --> 00:01:24,370 If the value present at mid, is it close to the value that we are searching for? 28 00:01:24,760 --> 00:01:28,480 Then in that case, I can return mid. 29 00:01:30,050 --> 00:01:30,240 OK. 30 00:01:30,670 --> 00:01:32,090 I am returning the index. 31 00:01:33,410 --> 00:01:34,030 Elusive. 32 00:01:34,280 --> 00:01:41,870 What I will do if the given value, if the value estimated is greater than the value that we are searching 33 00:01:41,870 --> 00:01:42,230 for. 34 00:01:42,710 --> 00:01:49,430 Then I can say that my value, that my key will lie on the left hand side of the mud. 35 00:01:49,880 --> 00:01:59,480 So this is made all the values on the left hand side are less than made and all the values on the right 36 00:01:59,480 --> 00:02:00,930 hand side are good downward. 37 00:02:01,610 --> 00:02:10,490 So if this middle value is greater than guey, which is our second case, then my key will only lie 38 00:02:10,760 --> 00:02:11,150 here. 39 00:02:11,720 --> 00:02:11,910 OK. 40 00:02:12,110 --> 00:02:13,640 And equals murder minus one. 41 00:02:14,210 --> 00:02:19,610 Similarly, as what you can do is start equals murder plus one. 42 00:02:20,870 --> 00:02:21,150 OK. 43 00:02:21,500 --> 00:02:23,560 Otherwise my answer will lie in. 44 00:02:23,690 --> 00:02:25,640 The key will lie in the right hand side. 45 00:02:26,000 --> 00:02:28,460 So I will start equals mid plus one. 46 00:02:30,370 --> 00:02:32,080 So this is all that we have to do. 47 00:02:32,800 --> 00:02:34,740 And when this wire loop terminated. 48 00:02:35,530 --> 00:02:35,780 OK. 49 00:02:36,100 --> 00:02:40,860 So when this rare look will damaged, that means start becomes good, then end. 50 00:02:41,170 --> 00:02:42,280 So this is the condition. 51 00:02:42,910 --> 00:02:45,370 So I will reach here if I reach here. 52 00:02:46,100 --> 00:02:48,730 That means the value. 53 00:02:48,760 --> 00:02:50,380 The key is not present. 54 00:02:50,440 --> 00:02:52,000 So I will return minus one. 55 00:02:52,970 --> 00:02:53,250 OK. 56 00:02:53,830 --> 00:02:58,500 So if this Vilo terminated this way look damaged naturally. 57 00:02:59,380 --> 00:03:00,190 What will happen. 58 00:03:01,480 --> 00:03:03,060 So when this my love will terminate. 59 00:03:03,760 --> 00:03:04,720 This will terminate. 60 00:03:04,780 --> 00:03:06,860 When start will become good then. 61 00:03:06,890 --> 00:03:07,200 And. 62 00:03:07,630 --> 00:03:13,120 And if that is the condition we have seen in the last example that the key was not there. 63 00:03:13,450 --> 00:03:15,070 So I will return minus one. 64 00:03:15,400 --> 00:03:18,070 Minus one is an invalid index. 65 00:03:18,190 --> 00:03:20,140 That is why I am returning minus one. 66 00:03:20,770 --> 00:03:23,800 So I am returning an invalid index. 67 00:03:24,920 --> 00:03:30,860 Otherwise, if the key is found, if this is the case, if the key is found, I will direct later turn 68 00:03:30,860 --> 00:03:34,190 made to these men, to these men. 69 00:03:34,520 --> 00:03:37,640 And this whole program will be completed. 70 00:03:37,970 --> 00:03:38,250 OK. 71 00:03:38,450 --> 00:03:42,370 So this whole program is comprised of this all function is completed. 72 00:03:43,220 --> 00:03:44,300 So let us write the code. 73 00:03:48,620 --> 00:03:51,500 Let's say the name of the file is Binary Search. 74 00:03:53,320 --> 00:03:58,980 Caught by new search, called for by new search, binary search. 75 00:04:00,630 --> 00:04:01,680 Dart, CBP. 76 00:04:05,620 --> 00:04:09,880 OK, so this was the court for leniency, which I am copping the whole gold. 77 00:04:17,790 --> 00:04:20,000 So this part will remain same. 78 00:04:20,820 --> 00:04:22,180 These things will be changed. 79 00:04:22,260 --> 00:04:23,250 So delete. 80 00:04:24,790 --> 00:04:29,860 They know the function will also get changed, so they know the function is binary search. 81 00:04:34,000 --> 00:04:39,640 It will take three and put three arguments, every side of the Eddie and the key. 82 00:04:40,710 --> 00:04:42,050 Now, I am taking input here. 83 00:04:42,990 --> 00:04:47,280 I am taking the really off key and here I will call the function 84 00:04:49,680 --> 00:04:50,370 binary. 85 00:04:52,800 --> 00:04:53,340 Serge. 86 00:04:55,040 --> 00:04:55,270 OK. 87 00:04:55,970 --> 00:05:03,140 So by is taking three barometer's as input at a size of dairy and the key, and it will return the position 88 00:05:03,320 --> 00:05:07,070 at which the geese present if the pollution equals minus one. 89 00:05:07,170 --> 00:05:12,500 Then the key is not found as the geese found at Perdition Buick's. 90 00:05:15,640 --> 00:05:22,450 Now, what I have to do, I have to first of all, I have to create two variables and start, which 91 00:05:22,450 --> 00:05:28,960 is initially zero and and which is initially N minus one. 92 00:05:29,630 --> 00:05:32,830 OK, so these are the two variables today need initially. 93 00:05:35,560 --> 00:05:36,730 Now, what do I want? 94 00:05:36,940 --> 00:05:42,190 I need a loop and this loop will continue. 95 00:05:42,330 --> 00:05:44,740 Violet Start is less than articles to end. 96 00:05:45,520 --> 00:05:52,870 So first of all, I will find the value of my ID so intimate a equals start plus. 97 00:05:53,710 --> 00:05:55,920 And by two. 98 00:05:56,380 --> 00:05:56,680 OK. 99 00:05:57,610 --> 00:05:58,690 Now the three cases. 100 00:05:58,870 --> 00:05:59,800 Case number one. 101 00:06:00,670 --> 00:06:10,630 If the value present at mid is a close to the value that we are searching for, then I can return mid. 102 00:06:13,380 --> 00:06:13,680 OK. 103 00:06:14,640 --> 00:06:15,240 Elusive. 104 00:06:17,130 --> 00:06:24,360 I will check if the value is impaired, made is greater than the value that we are searching for. 105 00:06:25,380 --> 00:06:28,830 Then the value can only be present on the left hand side. 106 00:06:29,340 --> 00:06:35,520 So end equals made minus one else. 107 00:06:35,940 --> 00:06:40,320 I can see that my value will be present on the right hand side. 108 00:06:40,650 --> 00:06:44,730 So start equals murd plus one. 109 00:06:45,660 --> 00:06:45,850 OK. 110 00:06:45,930 --> 00:06:47,250 So this is all that we have to do. 111 00:06:47,670 --> 00:06:56,220 And finally, if this VI looked at it this way, looked at it, that means that given key is not present, 112 00:06:56,340 --> 00:06:58,920 in that case I will return minus one. 113 00:07:00,120 --> 00:07:00,360 OK. 114 00:07:00,630 --> 00:07:03,480 So this is the old guard of binary search. 115 00:07:05,080 --> 00:07:05,860 Now, let's see. 116 00:07:08,540 --> 00:07:10,010 OK, so El's, if. 117 00:07:16,670 --> 00:07:22,370 So the number of elements are seven and the elements are OK. 118 00:07:22,460 --> 00:07:24,380 So I am giving unsorted input. 119 00:07:25,100 --> 00:07:29,510 So seven, six, five, four, three, two and one. 120 00:07:30,440 --> 00:07:32,620 And the key that we want to find is seven. 121 00:07:33,560 --> 00:07:35,760 So it is returning key not found. 122 00:07:36,240 --> 00:07:38,060 So by any searches, not working properly. 123 00:07:38,080 --> 00:07:38,390 Why? 124 00:07:38,690 --> 00:07:41,420 Because the important that we have given is unsorted. 125 00:07:41,810 --> 00:07:46,730 And the condition for using by search is that the input must be sorted. 126 00:07:47,970 --> 00:07:51,810 So what do we lose is, first of all, we all saw the input. 127 00:07:52,470 --> 00:07:55,000 So let us first start, Eddie. 128 00:07:55,790 --> 00:08:04,590 So I thought a comma, a plus and OK, so now that is sorted now by any such rule book. 129 00:08:04,830 --> 00:08:05,520 So let's see. 130 00:08:07,280 --> 00:08:14,200 Number of elements are seven and the elements are seven, six, five, four, three, two and one. 131 00:08:15,550 --> 00:08:16,960 So I want to search for seven. 132 00:08:17,940 --> 00:08:20,440 So key found at index six. 133 00:08:21,550 --> 00:08:24,200 So our output is coming out the right way. 134 00:08:28,760 --> 00:08:30,020 So this was the input. 135 00:08:31,240 --> 00:08:32,500 And I have converted. 136 00:08:33,800 --> 00:08:38,450 So after sorting, this will become one, two, three, four, five, six and seven. 137 00:08:38,690 --> 00:08:40,160 And I want to search for seven. 138 00:08:40,490 --> 00:08:43,650 So seven is present at index six somewhere. 139 00:08:43,670 --> 00:08:44,420 Output is right. 140 00:08:44,600 --> 00:08:44,890 OK. 141 00:08:49,050 --> 00:08:49,950 So one more time. 142 00:08:50,040 --> 00:08:52,710 Now, this time, I will give correct input. 143 00:08:53,120 --> 00:08:54,480 That is sort of the input. 144 00:08:54,990 --> 00:08:59,490 So one, two, three, four, five, six and seven. 145 00:09:00,090 --> 00:09:02,250 I want to search for let's have one. 146 00:09:03,510 --> 00:09:05,940 So we found at index zero. 147 00:09:10,730 --> 00:09:16,700 Namaroff elements are five and the elements are, let's say, one, two, three, four and five. 148 00:09:17,030 --> 00:09:18,470 Why am givings ordered and bought? 149 00:09:18,530 --> 00:09:21,080 Because this is the condition for using brain research. 150 00:09:22,010 --> 00:09:24,800 And I want to search for, let's say, four. 151 00:09:26,060 --> 00:09:28,700 So four is found at index three. 152 00:09:28,940 --> 00:09:29,600 So zero. 153 00:09:29,600 --> 00:09:30,980 One, two and three. 154 00:09:32,100 --> 00:09:33,210 Now, one more time. 155 00:09:34,460 --> 00:09:38,000 A number of elements are five and the elements are, let's say 10. 156 00:09:38,350 --> 00:09:38,770 Ten. 157 00:09:39,890 --> 00:09:40,950 Twenty three. 158 00:09:42,140 --> 00:09:42,630 Five. 159 00:09:43,020 --> 00:09:43,790 And let's see. 160 00:09:43,990 --> 00:09:44,880 Fifty 52. 161 00:09:46,020 --> 00:09:51,570 I want to search for 52, so key found at legs for. 162 00:09:53,800 --> 00:09:56,280 Now, let us test minus one case, okay? 163 00:09:56,730 --> 00:09:58,020 When the gays not present. 164 00:10:00,300 --> 00:10:08,210 So there are five elements and the elements are 20, 31, 45, 78 and Lenzi handled. 165 00:10:09,720 --> 00:10:12,390 I want to search for 252. 166 00:10:13,580 --> 00:10:14,980 So key not found. 167 00:10:15,960 --> 00:10:16,260 OK. 168 00:10:16,630 --> 00:10:19,350 So by new searches, working perfectly fine. 169 00:10:20,340 --> 00:10:22,920 Now, one optimization we can do is. 170 00:10:26,520 --> 00:10:28,440 So focus on this part. 171 00:10:29,250 --> 00:10:36,180 Start plus and and then this is in record and then I'm dividing by two. 172 00:10:37,540 --> 00:10:41,020 What is the maximum value of integer into Max? 173 00:10:43,150 --> 00:10:43,460 OK. 174 00:10:43,720 --> 00:10:45,860 Due to the power today, one minus one. 175 00:10:47,260 --> 00:10:49,150 So there may be a possibility. 176 00:10:50,710 --> 00:10:54,780 So suppose S and E are very big integers. 177 00:10:54,980 --> 00:10:57,930 OK, so S&P are very big integers. 178 00:10:58,000 --> 00:11:00,100 My area is very big. 179 00:11:01,180 --> 00:11:02,620 OK, so my area is very big. 180 00:11:02,920 --> 00:11:06,310 So S&P, the values of start and end are very big. 181 00:11:06,820 --> 00:11:11,140 So if you are writing two big integers, if you are writing to be contagious. 182 00:11:11,250 --> 00:11:15,840 There's a possibility that it may cross the value of intermix. 183 00:11:16,780 --> 00:11:17,020 Okay. 184 00:11:17,350 --> 00:11:19,360 You are adding two very big integers. 185 00:11:19,450 --> 00:11:24,310 So there might be a possibility that this the sum of these two. 186 00:11:24,760 --> 00:11:28,530 Now, some of these two becomes greater than intermix. 187 00:11:29,380 --> 00:11:33,920 And if that happens, we call it integer overflow. 188 00:11:35,340 --> 00:11:43,850 Wraparound will take place, a wraparound will be there, and our output star plus and will become negative. 189 00:11:44,070 --> 00:11:44,640 Why negative? 190 00:11:44,670 --> 00:11:46,860 Because the wrap around will be there. 191 00:11:47,550 --> 00:11:51,280 So this really start plus end will become negative and negative. 192 00:11:51,300 --> 00:11:53,700 Divided by two, you will get a negative index. 193 00:11:54,420 --> 00:11:55,620 You will get a negative index. 194 00:11:55,650 --> 00:11:57,110 They will live mid, will be negative. 195 00:11:57,450 --> 00:11:58,680 And then you will do this. 196 00:11:58,800 --> 00:12:03,170 AIFMD of made and made is negative. 197 00:12:03,660 --> 00:12:05,400 You will get segmentation fault. 198 00:12:05,450 --> 00:12:06,780 Or you can see it and Tamarrod. 199 00:12:07,770 --> 00:12:11,030 So if we will find murder with the help of this method start. 200 00:12:11,130 --> 00:12:13,200 Listen to what will happen. 201 00:12:13,500 --> 00:12:15,630 Ninety nine point nine nine percent. 202 00:12:15,750 --> 00:12:20,680 Your code is correct, but there might be immediate or flawed. 203 00:12:20,690 --> 00:12:21,830 Who can say it and diameter. 204 00:12:22,410 --> 00:12:23,640 So how we can avoid it. 205 00:12:27,200 --> 00:12:29,330 OK, so tell me start. 206 00:12:29,900 --> 00:12:32,990 And by two, can I start like this? 207 00:12:33,800 --> 00:12:37,010 Start plus and minus. 208 00:12:37,100 --> 00:12:38,180 Start my. 209 00:12:39,350 --> 00:12:40,490 So are these same. 210 00:12:42,490 --> 00:12:42,940 Let's see. 211 00:12:42,970 --> 00:12:46,670 So this value is stark way to bless, and I do. 212 00:12:47,320 --> 00:12:49,250 And this values start bless. 213 00:12:49,540 --> 00:12:51,380 And where do minus start? 214 00:12:51,430 --> 00:12:54,480 By two, which is start by two plus. 215 00:12:54,580 --> 00:12:55,450 And why two. 216 00:12:56,040 --> 00:12:56,830 So these. 217 00:12:58,600 --> 00:13:02,820 So this value and this value, they both are same. 218 00:13:03,160 --> 00:13:06,700 But in this case, you are adding two big integers. 219 00:13:07,150 --> 00:13:14,380 So they might be a possibility of integer overflow and bizzaro flow means crossing the maximum value, 220 00:13:14,800 --> 00:13:16,720 if you will, go ahead of intermix. 221 00:13:17,320 --> 00:13:19,180 We will call it overflow. 222 00:13:20,020 --> 00:13:23,860 But in this case, this is a big integer, big in danger. 223 00:13:23,980 --> 00:13:26,140 And this is also a big and danger. 224 00:13:26,230 --> 00:13:28,150 And you are taking dear friends. 225 00:13:28,960 --> 00:13:29,230 OK. 226 00:13:29,310 --> 00:13:30,800 So you are taking difference. 227 00:13:31,120 --> 00:13:37,300 So in this case, overflow can cannot be there or a flow situation can be there. 228 00:13:37,840 --> 00:13:39,670 So this is much better. 229 00:13:40,830 --> 00:13:41,160 OK. 230 00:13:41,830 --> 00:13:42,850 So we will use it. 231 00:13:43,360 --> 00:13:45,490 We will always use it. 232 00:13:46,640 --> 00:13:50,290 Now, if we have overflow, that means we will also have underflow. 233 00:13:51,150 --> 00:13:54,570 So underflow means your value is less than into minimum. 234 00:13:56,070 --> 00:13:56,270 OK. 235 00:13:56,510 --> 00:13:56,890 So. 236 00:14:00,850 --> 00:14:02,350 So this is Intiman 237 00:14:04,870 --> 00:14:05,860 and this is. 238 00:14:06,340 --> 00:14:12,790 And Max, so if you will cross over live into Max, we call it in Egypt overflow. 239 00:14:13,300 --> 00:14:19,120 Similarly, if we will go beyond A.M., I will call it underfloor and deja underfloor. 240 00:14:21,320 --> 00:14:27,950 So in this problem in Egypt or flaw by any search and digital flow might be there. 241 00:14:28,100 --> 00:14:32,330 So we have to handle this case also and how to handle this case. 242 00:14:34,160 --> 00:14:37,910 We will find made by another method, which is start. 243 00:14:37,940 --> 00:14:38,360 Plus. 244 00:14:40,390 --> 00:14:43,180 And minus start by two. 245 00:14:43,840 --> 00:14:44,160 OK. 246 00:14:44,440 --> 00:14:46,320 So we will always find mid. 247 00:14:46,390 --> 00:14:47,890 With the help of this method. 248 00:14:48,970 --> 00:14:55,390 Now, let's test this method number of elements out of five and elements are one, two, three, four 249 00:14:55,390 --> 00:14:55,870 and five. 250 00:14:56,200 --> 00:14:58,360 I want to search for, let's say, two. 251 00:14:59,410 --> 00:15:01,330 So we found that index one. 252 00:15:01,450 --> 00:15:01,680 OK. 253 00:15:02,710 --> 00:15:04,090 So a court is correct. 254 00:15:05,430 --> 00:15:08,220 So if you have any problem in buying this search, you can ask me. 255 00:15:08,640 --> 00:15:09,180 OK, guys. 256 00:15:09,510 --> 00:15:11,040 So this is it for this video. 257 00:15:11,100 --> 00:15:11,640 Thank you.