Order and Conquer: Binary Search

Today, we will look at a first simple but very useful algorithm: Binary Search. We will understand how it works, why it is so fast and what things we can do with it.

00:00 Prologue: Can we find the maximum or duplicates any faster?
02:52 How does Binary Search work?
05:02 Implementation
06:28 Worst case running time: intuition
07:49 Running time analysis
11:15 Extension: Which element is the closest?
13:47 More extensions: programming exercise
14:39 Recap

[TheDarkOne]

Very nice video!
Here's what I think of when I hear of binary search:
When I took a course on functional programming in haskell, a student walked up to the professor and asked "Why is binary search in Haskell so slow?"
The professor couldn't explain and the lecture soon ended. Investigation continued until late into the night.
In short: It's O(nlogn).
If you use an algorithm, check your data types. If something works great on arrays (or rather, an ordered, random-access structure), it is probably horrible for linked lists. Even simple operations like getting the length can be O(n).
Of cause there are linked list implementations which get around these issues. But there's more issues specific to lists in Haskell and other "purely" functional languages.

[thiernondiaye]

Incredible explanation precise and clear

[TECHN]

I ultimately have 2 criticisms, the first about looking for duplicates and the second about applying theory to practice.

With looking for duplicates, there is an algorithm, albeit, not in-array, of which is O(n) complexity:
- initialize a hash set
- iterate over the array
- check the hash set if the current array element exists, if so, there is a duplicate, otherwise, continue
- add the current element to the hash set
- repeat until you find the first duplicate, all the duplicates, or nothing else exists.

I know this isn't in-array, however, it is a single loop with constant time instructions.
Given the caveat of the algorithm having to be in-array, yes, the video is otherwise accurate.

Second criticism is about how fast binary search is in practice as most of the time, your data is not ordered, or if it is ordered, you asked for it to be ordered, and therefore, the time sorting the set must still be taken into account. In some cases, yes, you can sort the data either at build/compile time or during start time, however, if you have to sort at runtime for some reason, given a time complexity for a sorting algorithm, there is an inequality for an array of a given size which tells you the minimum number of times you search that data, given it doesn't change between searches, where binary search is always better than linear search. Again, the caveat with this is that the array must not be mutated from one search to the next.