Divide and Conquer
Learn about divide and conquer algorithms, with a focus on binary search and binary search trees.
StartKey Concepts
Review core concepts you need to learn to master this subject
Divide and Conquer Algorithms
Complexity of Binary Search
Iterative Binary Search
Base case in a binary search using recursion
Updating pointers in a recursive binary search
Binary Search Sorted Dataset
Operation of a Binary Search
Binary Search Performance
Divide and Conquer Algorithms
Divide and Conquer Algorithms
- Divide-and-conquer solves a large problem by recursively breaking it down into smaller subproblems until they can be solved directly.
- Divide-and-conquer works in three steps: divide, conquer, and combine.
- It is more efficient than brute force approaches.
- It is prone to stack overflow error due to the use of recursion.
Binary Search: Conceptual
Lesson 1 of 3
- 1With a sorted data-set, we can take advantage of the ordering to make a sort which is more efficient than going element by element. Let’s say you were looking up the word “Telescope” in the dictio…
- 2Play with this interactive visualization demonstrating binary search. Refresh the page to play again with a different list.
- 3How efficient is binary search? In each iteration, we are cutting the list in half. The time complexity is O(log N). A sorted list of 64 elements will take at most log 2 (64) = 6 compari…
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory