WEBVTT 00:00.150 --> 00:06.690 Hello again! In this video, we are going to continue looking at searching algorithms. The mismatch 00:06.690 --> 00:12.180 algorithm takes two iterator ranges, and it will try to find the first element in the ranges, which 00:12.180 --> 00:16.650 is different. If, for example, we give it these two vectors, 00:17.160 --> 00:23.610 it will notice that the element at the fourth index is different, and it will return a pair of iterators. 00:24.630 --> 00:29.340 The first member of this pair will be an iterator to the element in vector one. 00:29.820 --> 00:33.210 And the second member will be an iterator to the element in vector two. 00:34.950 --> 00:36.870 So here we have those two vectors. 00:36.870 --> 00:39.060 We have a simple function for printing them out. 00:42.120 --> 00:47.880 And then we call the mismatch algorithm. So we give the iterator range for vec1 and the 00:47.880 --> 00:49.310 iterator range for vec2. 00:49.560 --> 00:53.040 And this will find the first mismatched element in the range. 00:55.180 --> 01:00.220 If the algorithm gets to the end of either one of the vectors, without finding a discrepancy, then 01:00.220 --> 01:03.280 it will put the end iterator in the member for that vector. 01:09.300 --> 01:10.090 So there we are. 01:10.110 --> 01:16.770 It found the mismatch at index 3. And the element in vec1 is 3 and the element in vec2 01:16.770 --> 01:17.460 is 2. 01:20.250 --> 01:24.750 And we just did that by getting the iterators from the pair and then dereferencing them. 01:26.610 --> 01:32.530 There are three algorithms which will take an iterator range and a predicate callable object, and 01:32.550 --> 01:37.890 they will check whether this predicate is true for some of the elements, all of the elements or none of 01:37.890 --> 01:38.460 the elements. 01:40.320 --> 01:44.130 So all_of() will return true if the predicate is true for every element. 01:44.880 --> 01:45.160 none_of() 01:45.180 --> 01:45.900 will return 01:45.900 --> 01:52.770 true, if the predicate is false for every elements. And any_of() will return true if the predicate 01:53.250 --> 01:55.410 is true for some of the elements. 01:59.320 --> 02:00.970 So here is our vector. 02:01.840 --> 02:07.240 We have two lambda expressions, one for an odd elemen and one for an even element. 02:07.480 --> 02:10.160 And we use those as the predicates for those functions. 02:10.180 --> 02:11.980 So we have all the permutations. 02:13.300 --> 02:19.480 So if all the elements are odd, then we expect to see that. If they are all even we expect to see that. 02:20.140 --> 02:22.690 If some elements are odd - and so on. 02:26.500 --> 02:33.280 So with this vector, some elements are odd and some elements are even. If I change this, so all the 02:33.280 --> 02:36.700 elements are odd, then we will get a different result. 02:40.540 --> 02:46.080 And there we are. All the elements are odd, some elements are odd. So this will return true if all 02:46.100 --> 02:50.200 are as well, and no elements in this vector are even. 02:52.510 --> 02:54.970 And just to make sure, let's do it for even numbers. 03:00.120 --> 03:02.100 OK, I am sure you get the idea! 03:03.510 --> 03:08.660 We all know about the find() algorithm, but if you have elements which are already sorted, then find 03:08.670 --> 03:10.920 is not the most optimal algorithm. 03:11.310 --> 03:16.020 You can actually use a much better one, which is much faster, and that is binary search. 03:17.190 --> 03:22.110 So this works the same way. We give it the iterator range, and the thing that we looking for. 03:22.770 --> 03:27.870 And it returns true if the range contains that value or that object. 03:31.350 --> 03:32.910 So we have our vector again. 03:33.210 --> 03:38.070 We sort it before we call binary search, because otherwise the binary search will not give the 03:38.070 --> 03:38.640 right answer. 03:39.450 --> 03:44.100 And then we call it. So we give the iterator range of the vector and we are looking for the element 03:44.100 --> 03:44.910 with value 4. 03:47.670 --> 03:50.910 So the vector contains 4, and it does not contain 8. 03:52.410 --> 03:54.300 And finally, the includes algorithm. 03:54.630 --> 03:56.520 This takes two iterator ranges. 03:56.790 --> 03:59.940 Again, it assumes that the iterator ranges are sorted. 04:01.230 --> 04:02.070 This will be return a bool 04:03.720 --> 04:09.540 If the first range contains all the elements in the second range, this will return the true, otherwise 04:09.540 --> 04:09.990 false. 04:11.310 --> 04:12.660 So let's look at this. 04:14.070 --> 04:16.440 So we are going to use strings now. Our famous 04:16.440 --> 04:19.740 "Hello world" string and also the vowels string. 04:21.930 --> 04:28.470 So we sort the strings first, because the algorithm expects that, and then we call includes(). we give 04:28.470 --> 04:32.100 the iterator range for "Hello world" and the iterator range for vowels. 04:32.940 --> 04:39.240 So if "Hello world" contains every character in vowels at least once, this will return true. 04:40.170 --> 04:41.940 So what do you think we'll get? 04:46.790 --> 04:52.430 So these are the sorted strings that the algorithm will work on. And "Hello world" does not contain 04:52.430 --> 04:53.660 all the characters in vowels. 04:58.320 --> 05:03.060 If we replace this with a string which does contain all the vowels, then we should get a different 05:03.060 --> 05:03.390 answer. 05:06.670 --> 05:10.300 And there we are, so now we do have all the vowels in our search string. 05:10.960 --> 05:12.520 Okay, so that's it for this video. 05:13.000 --> 05:16.000 I'll see you next time, but until then, keep coding!