Coding Patterns: Binary Search

Search - Find some target in a data structure Linear search - Scan from left to right looking for the target. Return as soon as you see the target. With a linear search you're cutting the search space by one element on each iteration which leads to an O(n) solution. Binary search is a more efficient way to search. Instead of scanning through elements one by one (as in linear search), binary search starts by comparing the target value to the middle element. The comparison allows us to get rid of half the search space on each comparison. Repeatedly cut the search space in half on each iteration which leads to a O(log(n)) solution. Binary search is a more efficient way to search but the search space needs to be sorted. You can binary search for: - An element in a data structure - A value Will usually not have to do binary search straight up but would have to do a modified binary search. Time complexity: log(n) Space complexity: O(1) Common pitfalls: - Binary search only works on sorted data. - Infinite Loops - Not updating the bounds correctly - Overflow in Mid Calculation _________________________________________________ 00:00 - Binary Search Explained 10:48 - Basic Binary Search 21:25 - Binary Searching for a Value 35:59 - Modified Binary Search 49:56 - Time/Space Complexities & Common Pitfalls