1 00:00:02,180 --> 00:00:03,930 Hey, guys, what's up? 2 00:00:04,550 --> 00:00:13,040 So today we are going to learn binary search, OK, so the problem with the linear search is that it 3 00:00:13,040 --> 00:00:17,970 doesn't take into consideration whether the given is sorted or sorted. 4 00:00:18,290 --> 00:00:22,490 OK, so we will use binary search for software that is. 5 00:00:23,100 --> 00:00:29,480 So there's a condition, condition used by news such as that area must be sorted. 6 00:00:30,440 --> 00:00:34,970 OK, so binary search can only be applied if the given that is sorted. 7 00:00:35,300 --> 00:00:36,910 If that is unsorted. 8 00:00:37,430 --> 00:00:39,560 If I have unsorted. 9 00:00:39,560 --> 00:00:39,880 Eddie. 10 00:00:41,160 --> 00:00:47,970 Then binary search cannot be applied, we have to apply linear search only. 11 00:00:48,450 --> 00:00:53,520 OK, so linear search is the only option if we have unsorted every. 12 00:00:54,560 --> 00:00:59,090 But if we have sorted that, we will always use binary search. 13 00:01:00,290 --> 00:01:07,340 OK, so let's see, so we will take an example and we will try to understand how binary search works. 14 00:01:08,640 --> 00:01:14,940 So suppose my ETAs, so it must be sorted, so let's see. 15 00:01:21,860 --> 00:01:29,570 So these are indexes zero, one, two, three, four, five, six and seven, and let's say the values 16 00:01:29,570 --> 00:01:37,810 are two, four, five, eight, 20, 23, 40 and 49. 17 00:01:38,840 --> 00:01:40,070 These are the values. 18 00:01:41,230 --> 00:01:48,270 For example, I want to search for let's say I want to search for food, so how my new search works, 19 00:01:48,610 --> 00:01:50,100 it takes two pointers. 20 00:01:50,380 --> 00:01:53,740 So this is a start and this is end. 21 00:01:54,580 --> 00:01:57,380 OK, so then it will calculate. 22 00:01:57,880 --> 00:02:00,160 So Americans start plus. 23 00:02:00,160 --> 00:02:06,500 And by doing that is zero plus seven by two. 24 00:02:06,760 --> 00:02:08,690 So three point five, which is three. 25 00:02:09,190 --> 00:02:09,669 So. 26 00:02:10,699 --> 00:02:19,760 My mate is here now, there are three possibilities, so first possibility number one, if the value 27 00:02:20,000 --> 00:02:21,400 president had made. 28 00:02:22,630 --> 00:02:26,690 Is it close to the given we're lucky if this is the case. 29 00:02:27,010 --> 00:02:27,960 I will return. 30 00:02:29,050 --> 00:02:41,080 OK, so I found the key and the key is present at the next second possibility if the value added is 31 00:02:41,080 --> 00:02:42,370 greater than the key. 32 00:02:44,120 --> 00:02:52,550 So in this case, for example, it is greater than four, then I can say that my answer, that key will 33 00:02:52,550 --> 00:02:54,530 lie only in this part. 34 00:02:55,400 --> 00:03:00,180 OK, we cannot lie here, so I will discard this part. 35 00:03:00,980 --> 00:03:07,770 So what I will do and it was made minus one, so my end will come here. 36 00:03:09,050 --> 00:03:11,540 OK, and how can I discard this part? 37 00:03:11,930 --> 00:03:16,130 Because I know this is amid all these values. 38 00:03:16,130 --> 00:03:23,020 On the left hand side are smaller than mud and all the values on the right hand side are greater than 39 00:03:23,030 --> 00:03:23,290 mud. 40 00:03:23,570 --> 00:03:29,460 So these values are less than made and these values are then made because my ad is certain. 41 00:03:29,720 --> 00:03:39,950 So if the value present at Miller is greater, then that means we can only only only lie in the left 42 00:03:39,950 --> 00:03:43,520 part so I can discard the right part. 43 00:03:43,610 --> 00:03:44,040 OK. 44 00:03:44,690 --> 00:03:47,720 And similarly, if. 45 00:03:50,150 --> 00:03:55,910 Murder is a less denki then, so this is my murder. 46 00:03:56,690 --> 00:03:58,490 This is right and this is left. 47 00:03:58,880 --> 00:04:00,780 So right values are greater than murder. 48 00:04:02,360 --> 00:04:11,330 So if my murder if the that murder is less stinky, then my answer will only lie in the right part. 49 00:04:11,580 --> 00:04:13,100 In that case, I will. 50 00:04:14,400 --> 00:04:17,829 Ignore the left part and what I will do. 51 00:04:17,910 --> 00:04:25,710 Start equals method plus one, so many will come here so they start will come here. 52 00:04:26,940 --> 00:04:31,180 And my problem is not only this, I have to search only on this part. 53 00:04:32,400 --> 00:04:37,110 OK, so let's take an example and we will see what happens. 54 00:04:38,820 --> 00:04:39,360 So. 55 00:04:44,680 --> 00:04:54,370 So zero, one, two, three, four, five and six, and the values are two, five, eight. 56 00:04:55,440 --> 00:05:07,710 13, 15, 20 and 25, and I want to search for value, let's say Geike was search for five, OK, so 57 00:05:08,130 --> 00:05:09,780 first of all, this is start. 58 00:05:10,050 --> 00:05:11,070 This is my start. 59 00:05:11,370 --> 00:05:20,550 And this is my and now I will calculate made so many calls start, which is zero plus and which is six 60 00:05:20,550 --> 00:05:21,330 by two. 61 00:05:21,750 --> 00:05:25,140 So Mayday's three now this is my murder. 62 00:05:26,550 --> 00:05:30,420 So compare the value is 13 equals five. 63 00:05:30,420 --> 00:05:32,850 No logic 13. 64 00:05:32,860 --> 00:05:33,660 Guerdon five. 65 00:05:33,690 --> 00:05:35,010 Yes, the condition is true. 66 00:05:35,220 --> 00:05:37,440 My answer will lie in the left part. 67 00:05:37,650 --> 00:05:39,030 So I will discard this. 68 00:05:41,230 --> 00:05:47,710 So and it was made minus one, so that is three, minus one at two. 69 00:05:48,130 --> 00:05:49,240 So this is my end. 70 00:05:50,020 --> 00:05:51,130 This is my end. 71 00:05:52,970 --> 00:06:02,780 Now I will again calculate so murder equals start, which is zero, and which is two by two, so it 72 00:06:02,780 --> 00:06:03,830 is coming out to be one. 73 00:06:04,100 --> 00:06:05,360 So this is murder. 74 00:06:06,290 --> 00:06:07,820 This is murder. 75 00:06:08,150 --> 00:06:11,730 Now, again, I will compare is five close to five. 76 00:06:11,910 --> 00:06:12,500 Yes. 77 00:06:13,040 --> 00:06:18,050 Then what I will do, I will return mid, return mid. 78 00:06:18,350 --> 00:06:20,330 So I will return the next one. 79 00:06:21,260 --> 00:06:21,660 OK. 80 00:06:21,680 --> 00:06:23,780 So this is how by research book. 81 00:06:25,200 --> 00:06:26,820 Now, let's take one more example. 82 00:06:29,970 --> 00:06:33,150 So suppose the adays. 83 00:06:39,910 --> 00:06:48,790 Zero, one, two, three, four, five and six, and let's say the values are one, four, five, 10, 84 00:06:49,210 --> 00:06:56,770 12, 18 and 25 and I want to search for, let's say, 25, OK? 85 00:06:57,010 --> 00:06:59,080 I want to search for value 25. 86 00:07:00,880 --> 00:07:02,190 So this is my start. 87 00:07:02,890 --> 00:07:04,180 This is my end. 88 00:07:05,540 --> 00:07:14,740 First of all, calculate the milk so many medicos start plus and buy two, so many clothes, three. 89 00:07:15,410 --> 00:07:17,450 OK, so this is my mid. 90 00:07:18,860 --> 00:07:21,780 Now, compare is 10 equals 25. 91 00:07:21,800 --> 00:07:28,190 No, the second condition is stronger than 25, no, and less than 25. 92 00:07:28,340 --> 00:07:30,580 I guess the value is less than key. 93 00:07:30,890 --> 00:07:38,480 So I will search on the right hand side that is and equals three start equals murder plus one. 94 00:07:38,810 --> 00:07:40,950 So much is three plus one. 95 00:07:41,510 --> 00:07:42,570 So this is four. 96 00:07:42,670 --> 00:07:48,080 So now this is my updated start and I will discard this whole part. 97 00:07:49,310 --> 00:07:56,750 Now, what I will do, I will calculate again, so Americans, you start there's four and there's six 98 00:07:56,750 --> 00:07:59,950 by two, so is coming out to be five. 99 00:07:59,960 --> 00:08:01,370 So this is my mid. 100 00:08:03,640 --> 00:08:13,550 Now, compare is 18, close to 25, now is 18 and then 25 now is 18, less than 25. 101 00:08:13,610 --> 00:08:14,080 Yes. 102 00:08:14,650 --> 00:08:19,090 So what I will do is start equals murder plus one. 103 00:08:19,780 --> 00:08:22,450 So it is five plus one. 104 00:08:22,720 --> 00:08:24,420 So start equals six. 105 00:08:24,820 --> 00:08:26,560 So discard the left hand side. 106 00:08:29,140 --> 00:08:32,020 Now, this is my start. 107 00:08:33,340 --> 00:08:42,429 OK, now I will calculate Made against America's Start plus, and by doing so, it is coming out to 108 00:08:42,429 --> 00:08:43,450 be six. 109 00:08:43,840 --> 00:08:44,650 Now compare. 110 00:08:45,190 --> 00:08:48,100 So is AOF six. 111 00:08:48,130 --> 00:08:49,350 That is 25. 112 00:08:49,690 --> 00:08:51,040 So is 25. 113 00:08:51,040 --> 00:08:52,310 Equals 25. 114 00:08:52,380 --> 00:08:54,650 Yes, the condition is true. 115 00:08:55,000 --> 00:09:02,850 I will return MD and Maydays six, so I will return six and add the next six. 116 00:09:02,870 --> 00:09:04,630 The value 25 is present. 117 00:09:05,230 --> 00:09:07,940 OK, so this is how by new search work. 118 00:09:08,380 --> 00:09:12,520 And now let us take one more example where the key will not be found. 119 00:09:13,180 --> 00:09:15,780 OK, so this is my area. 120 00:09:23,100 --> 00:09:34,320 Zero, one, two, three, four, five, and let's say six and seven, and the values are two, three, 121 00:09:34,710 --> 00:09:46,170 four, eight, 12, 15, 20, 27, and the values that I want to search for is let's say five of five 122 00:09:46,170 --> 00:09:47,120 is not present here. 123 00:09:47,400 --> 00:09:49,100 I want to search for five. 124 00:09:50,490 --> 00:09:51,870 So this is my start. 125 00:09:52,530 --> 00:10:01,440 This is my and now let us convert the value of the murders of miracles, start bless and buy two. 126 00:10:01,920 --> 00:10:04,710 So it is coming out to be three point five, which is three. 127 00:10:04,710 --> 00:10:07,140 Integer upon integer will be in integer. 128 00:10:07,920 --> 00:10:13,410 So this is my ID now compare it equals five. 129 00:10:13,740 --> 00:10:16,230 No eight then five. 130 00:10:16,410 --> 00:10:17,040 Yes. 131 00:10:17,280 --> 00:10:23,850 So what I will do and it was made minus when that is what is the value of three. 132 00:10:24,120 --> 00:10:27,420 So three minus one so and equals two. 133 00:10:27,870 --> 00:10:30,240 So this is the new value of end. 134 00:10:31,200 --> 00:10:34,410 And what I will do, I will discard the right hand side. 135 00:10:36,360 --> 00:10:46,410 Now, again, calculate what is the value of milk, which is start plus and buy to sell to buy two is 136 00:10:46,410 --> 00:10:46,740 one. 137 00:10:47,160 --> 00:10:48,120 So this is my. 138 00:10:49,050 --> 00:10:49,980 This is made. 139 00:10:50,940 --> 00:10:52,330 Now compare the value of milk. 140 00:10:52,770 --> 00:10:54,770 So is three equals five. 141 00:10:54,990 --> 00:10:55,460 No. 142 00:10:55,980 --> 00:10:57,960 So is triggered then five. 143 00:10:58,180 --> 00:10:58,690 No. 144 00:10:59,130 --> 00:11:00,000 So it's three. 145 00:11:00,000 --> 00:11:00,880 Less than five. 146 00:11:01,130 --> 00:11:01,520 Yes. 147 00:11:01,770 --> 00:11:06,820 So what I will do is start equals murd plus one. 148 00:11:07,380 --> 00:11:08,630 So what is the value of made. 149 00:11:09,890 --> 00:11:10,800 So one plus one. 150 00:11:10,920 --> 00:11:14,940 The value of start is to so start will reach here. 151 00:11:16,590 --> 00:11:26,160 Now again calculate the value of milk which is start plus and by doing so four by two is two. 152 00:11:26,460 --> 00:11:27,630 So this is my mid. 153 00:11:28,380 --> 00:11:29,400 This is mid. 154 00:11:30,320 --> 00:11:40,650 Now, what I will do, I will compare the values, so is four equals five no is for them, five no. 155 00:11:41,060 --> 00:11:43,280 So is for less than five. 156 00:11:43,460 --> 00:11:44,000 Yes. 157 00:11:44,270 --> 00:11:48,780 So what I will do is start equals murder plus one. 158 00:11:49,370 --> 00:11:52,070 So what is the value of Modesto's or two. 159 00:11:52,070 --> 00:11:52,580 Plus one. 160 00:11:52,910 --> 00:11:56,180 So start is three, so my start will come here. 161 00:11:57,720 --> 00:11:58,950 So this is my start. 162 00:11:59,550 --> 00:12:04,380 Now, what happened is start is three and is two. 163 00:12:06,920 --> 00:12:10,410 This is a start and this is end, OK? 164 00:12:10,610 --> 00:12:15,050 So what happened here is start becomes greater than end. 165 00:12:15,560 --> 00:12:25,220 So if this is the condition, that means I can say I will stop and I will report that the key is not 166 00:12:25,880 --> 00:12:28,220 present, key not found. 167 00:12:28,670 --> 00:12:37,550 OK, so if my start becomes an end, I will stop and I will report my answer that the given key is not 168 00:12:37,550 --> 00:12:39,110 present in the Eddie. 169 00:12:41,270 --> 00:12:44,690 OK, so this is how binary search works. 170 00:12:45,840 --> 00:12:50,220 Now, let us try to find how many number of steps by new search will take. 171 00:12:51,390 --> 00:12:58,410 OK, so what I am doing, I am calculating the value of the method, which is a start plus and two, 172 00:12:59,040 --> 00:13:04,560 and then I'm comparing with key, I'm comparing these two values. 173 00:13:05,130 --> 00:13:11,310 And each time I'm comparing these values, what I'm doing, I am reducing my number of elements on which 174 00:13:11,310 --> 00:13:12,060 I have to search. 175 00:13:12,900 --> 00:13:15,900 OK, so if is Denki. 176 00:13:17,320 --> 00:13:19,190 And it was made of minus one. 177 00:13:19,480 --> 00:13:23,740 So if there were any elements, so I suppose there are any elements. 178 00:13:25,110 --> 00:13:32,820 This is made and if this is good denki what I did, I will put my pointer here. 179 00:13:33,360 --> 00:13:34,700 This is start and this is end. 180 00:13:34,980 --> 00:13:37,790 So this is my new search space. 181 00:13:39,030 --> 00:13:41,310 So this is my new search space. 182 00:13:41,870 --> 00:13:44,980 We will only be present here, otherwise we will not be there. 183 00:13:45,540 --> 00:13:53,010 So initially I was searching on any elements then I am searching on envie two elements. 184 00:13:55,290 --> 00:14:02,090 OK, and we will repeat the same process here also, I will admit I will come key and similarly, if 185 00:14:02,220 --> 00:14:07,320 it is less than what I will do, start equals murder plus one. 186 00:14:07,620 --> 00:14:10,950 So start will come here and I will discard this part. 187 00:14:11,520 --> 00:14:14,010 So again, these are and by two elements only. 188 00:14:14,940 --> 00:14:19,330 So what I am doing, I am decreasing my search space by two. 189 00:14:19,620 --> 00:14:22,200 So next time I will search on and buy four elements. 190 00:14:24,580 --> 00:14:26,930 Then end by eight elements and so on. 191 00:14:27,580 --> 00:14:34,840 OK, so each time I am reducing my search of space, the search space means the number of elements on 192 00:14:34,840 --> 00:14:36,060 which you have to search. 193 00:14:36,070 --> 00:14:37,550 You have to perform a search operation. 194 00:14:38,380 --> 00:14:39,550 So what is happening here? 195 00:14:39,880 --> 00:14:41,380 Initially, I have to search. 196 00:14:43,420 --> 00:14:51,550 And elements, then I will calculate and then compare, then I have to search in and buy two elements, 197 00:14:53,110 --> 00:14:56,010 then I have to search for and buy four elements. 198 00:14:56,020 --> 00:15:01,150 I will search in and buy four elements for the gunky and it will keep going on. 199 00:15:02,050 --> 00:15:06,620 Let's see the number of steps in binary search is key. 200 00:15:07,140 --> 00:15:16,840 OK, let's say a binary search takes steps in binary search take steps so finally end upon to the power 201 00:15:16,990 --> 00:15:17,350 key. 202 00:15:19,050 --> 00:15:28,200 OK, so when this Minnesota will stop, when there is only one element in the area so and to a close 203 00:15:28,210 --> 00:15:37,200 one, that is this Minnesota will stop only when there is only one element in the area because I cannot 204 00:15:37,320 --> 00:15:39,630 divide one element into two 1/2. 205 00:15:39,900 --> 00:15:45,780 OK, so and it goes to the patchwork taking log on both the sides. 206 00:15:46,050 --> 00:15:54,300 So log and it goes back log to and K equals log and with the base to. 207 00:15:54,720 --> 00:15:58,260 And I told you that constant doesn't matter. 208 00:15:58,650 --> 00:16:02,880 So Keiko's log of N constant doesn't matter. 209 00:16:03,270 --> 00:16:04,980 So give us the number of steps. 210 00:16:06,180 --> 00:16:14,400 And this is a log and it's a binary search, binary search takes log off and steps. 211 00:16:16,240 --> 00:16:18,570 So what is the time complexity of binary search? 212 00:16:18,930 --> 00:16:24,420 It is big off log and and linear search time. 213 00:16:24,420 --> 00:16:26,620 Complexity of linear search was off. 214 00:16:26,640 --> 00:16:30,390 And so this is for sorted Eddie. 215 00:16:33,030 --> 00:16:42,150 OK, so if the given that is sorted, then binary search is much, much more efficient than linear search. 216 00:16:42,970 --> 00:16:48,630 OK, so this is it for this video and next video, I will write the code for Binary Search. 217 00:16:49,220 --> 00:16:52,070 OK, so if you have any doubt, feel free to ask. 218 00:16:52,140 --> 00:16:52,740 Thank you.