I just watched the short for binary search and I'm having trouble understanding how making a conditional of (max < min) would mean that the number is not in your array (timestamp 04:05). I get that if max was less than min then the list is not sorted properly, but they were saying that if max is less than min, "you went too far." Why does (max < min) mean that the number is not in your list? Thanks!
1 Answer
in case we have a single element left in the array, max and min would be equal. the midpoint is calculated, and we check whether array[midpoint] is equal to the value we're looking for.
if the previous condition is not true, namely array[midpoint] is NOT equal to the value we're looking for, the algorithm still proceeds further and either sets max to a lower value or sets min to a greater value. in either case max would be less than min (see why?).
in the next iteration/recursive call we wouldn't wanna proceed further than that because we would have no elements in the array left to check against.
-
I see, so although you only have one value left, assuming the search continues on, it will search between min and midpoint -1 or midpoint +1 to max. Because of the +1 or -1 and the fact that the midpoint, min, and max (before adding or subtracting 1) is all the same number, the new min will end up larger than max or the new max will end up be smaller than the min. Thanks! PS - sorry for the suuuper late response, had to take a break from the lessons due to life and stuff... Back at it again now! Commented Nov 20, 2015 at 8:43