WEBVTT 00:00.210 --> 00:05.610 Hello again! In this video, we are going to look at searching algorithms. So these are algorithms which 00:05.610 --> 00:07.740 search within iterator ranges. 00:09.060 --> 00:14.850 When we looked at the string interface for the library string, we saw that it has several member functions 00:14.850 --> 00:16.590 for searching within strings. 00:17.190 --> 00:21.990 For example, if we call find_first_of(), then it will search in the object that it was called on, 00:22.320 --> 00:25.680 and return the first occurrence of an element from its argument. 00:26.280 --> 00:29.580 And we used that to find the first vowel in the string "Hello world". 00:32.340 --> 00:35.700 There is a generic algorithm version of this function, 00:35.910 --> 00:41.330 find_first_of(), and this can be used with any container. Or in fact, anything which supports iterator 00:41.340 --> 00:41.880 ranges. 00:42.810 --> 00:48.780 If we wanted to do this example again, using the generic algorithm, then we would pass the beginning 00:48.780 --> 00:53.910 and end iterators for "Hello World" as the first two arguments, and then the begin and end iterators 00:53.910 --> 00:57.060 for "vowels" as the second two arguments. 00:58.290 --> 01:02.850 This will return, and iterator to the first vowel in "Hello world". 01:03.510 --> 01:05.160 If there is no match, then it returns 01:05.160 --> 01:11.010 the invalid iterator, so we need to check that. And then, if we get a valid iterator, we can use 01:11.010 --> 01:11.220 it. 01:12.910 --> 01:19.750 This algorithm uses the equality operator by default. The equality operator of the element's type. String 01:19.750 --> 01:20.440 in this case. 01:21.340 --> 01:25.960 And in fact, I think all the examples in this video and the next one use the equality operator. 01:26.350 --> 01:31.330 So that's why the equality operator is so important, because it is used for matching and searching for 01:31.330 --> 01:34.690 data. And in programming, that is something we do all the time. 01:35.140 --> 01:36.490 So here is our code. 01:36.490 --> 01:42.840 We have the Hello World string. We have the vowel string. We call find_first_of() with the iterators for 01:42.850 --> 01:49.030 "Hello World" and the vowels, and then we check the return value and we use that to get the data. 01:49.510 --> 01:54.340 Normally, you would not be interested in the index position of the element. The actual data is more 01:54.340 --> 01:54.820 useful. 01:55.210 --> 01:59.890 But in these examples, I am going to show it, as it helps to understand what the algorithm is actually 01:59.890 --> 02:00.280 doing. 02:03.050 --> 02:07.160 So let's try this out. And we get the first vowel is 'e' at index 1. 02:08.810 --> 02:15.110 When we did our search, it found an element with the value 'e', which matches, and it return an 02:15.110 --> 02:16.190 iterator to that element. 02:17.000 --> 02:21.050 If there had been no match, it would have carried on past the last element and returned 02:21.050 --> 02:28.280 the end iterator. if we want to do another search to find the next vowel, then we can just call 02:28.280 --> 02:31.580 find_first_of() again. Then we pass the starting point. 02:31.790 --> 02:37.730 We do not use this iterator because it will start with the letter 'e' and return the same value again. 02:38.300 --> 02:40.370 And if we keep doing that, we get an infinite loop. 02:41.360 --> 02:43.780 We need to start again from the next iterator. 02:44.360 --> 02:46.310 So the next vowel from here, 02:47.440 --> 02:48.970 before the end of the container. 02:51.820 --> 02:56.980 So we need to use the iterator range from the iterator after the result, to the end. 02:58.030 --> 02:59.770 And then the rest of the code will be the same. 03:02.760 --> 03:09.060 So we have got the same code that we had before, for finding the first vowel. And then we call it again 03:09.390 --> 03:10.440 to find the second vowel. 03:11.070 --> 03:15.600 We use the iterator following the result as the start of the rate of change. 03:18.710 --> 03:25.370 And if we get the first vowel is 'e' at index 1, the second vowel is 'o' at index 4. And 03:25.370 --> 03:29.510 then we could call it again, to get the next index. 'o' at index 03:30.020 --> 03:30.440 seven. 03:32.700 --> 03:37.530 The adjacent_find() algorithm will look for two neighbouring elements which have the same value. 03:38.280 --> 03:45.720 So if we called this on "Hello world", it would find the double 'l' as the first match, and it would return 03:45.720 --> 03:47.790 an iterator to the first letter 'l'. 03:50.400 --> 03:55.650 So to call this, we just pass one iterator range, and it will work out where the first match 03:55.650 --> 03:55.830 is. 04:00.160 --> 04:03.820 Found adjacent elements with value 'l' at index 2. 04:06.210 --> 04:11.910 If we want more than two elements with the same value, and we know which value we want, then we can 04:11.910 --> 04:13.200 use search_n(). 04:13.200 --> 04:18.960 So this will look for 'n' successive elements which have the same given value. And we can say 04:18.960 --> 04:22.170 what we want the value of 'n' to be, and we have to say what the value is. 04:24.630 --> 04:29.530 For example, we could have a vector of ints, and then we could call this with begin() and end() for the entire 04:29.530 --> 04:29.940 vector. 04:30.510 --> 04:33.300 And then 2 is the length of the sequence. 04:33.720 --> 04:35.130 And 3 is the value. 04:35.610 --> 04:41.370 So we want the first sequence of 2 elements with the value 3, which should be those two. 04:42.410 --> 04:43.820 And let's try that out. 04:45.620 --> 04:48.080 2 elements with value 3, starting at index 5. 04:49.730 --> 04:51.690 (Two, three, four five, yep) 04:54.260 --> 04:59.690 And then finally, there is a search() algorithm which is completely different from search_n(), 04:59.690 --> 05:02.150 but I did not choose these names! 05:04.390 --> 05:08.080 So this is similar to searching for a substring within a string. 05:08.670 --> 05:14.070 We give it two iterator ranges and this will look for the first complete occurrence of that 05:14.070 --> 05:15.430 iterator range in the first one. 05:16.030 --> 05:21.760 So if we are doing this with strings again, we have our "Hello world" string. So that is the first two 05:21.760 --> 05:23.020 iterators, which is the first pair. 05:23.740 --> 05:26.290 And then we have a substring, so that would be the second path. 05:27.130 --> 05:31.540 And this is going to look for the first occurrence of "wo" in "Hello world". 05:37.140 --> 05:40.860 So the substring "wo" is found its index 6. 05:43.190 --> 05:48.080 If I make it something that is not in the string. So "wol". 05:52.220 --> 05:54.920 And there is no result. So perhaps I should say, 06:03.650 --> 06:04.400 "No match found". 06:05.090 --> 06:06.740 Okay, so that substring is not found. 06:08.000 --> 06:09.680 Okay, so that it is for this video. 06:10.310 --> 06:11.210 I'll see you next time. 06:11.210 --> 06:13.310 But until then, keep coding!