Binary Search
I always get confused with the bounds.
Resources
- Binary Search tutorial (C++ and Python)
- Biggest learning here is that binary search also works on an array that looks like
[true, true, true, false, false, false]
!
- Biggest learning here is that binary search also works on an array that looks like
- Competitive Programmer’s Handbook
Code that I use for Competitive Programming:
Does binary search work if there are duplicate values??
Yes, as long as the function you’re searching over is Monotonic Function. (ACTUALLY, it depends on the problem). Look at the example application below, we can’t have duplicate values.
You can also use the built in library in C++, since it is faster. But I also encourage you when needed to write it yourself.
- https://cplusplus.com/reference/algorithm/lower_bound/ Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.
- https://cplusplus.com/reference/algorithm/upper_bound/ returns an iterator pointing to the first element in the range
[first,last)
which compares greater than val.
Finding first number smaller than “val”?
Applications
You can boil down a lot of search problems that don’t seem like search problems at first, but they are.
Ex: Finding the smallest solution
Related
Actually, the idea of splitting the problem in half really comes more more often than I thought. It allows us to go from to for lots of problems. These are some of the ideas:
- Lowest Common Ancestor (Binary Lifting)
- Successor Graph → computing
- Tree Query → finding the ancestor
- Fenwick Tree and
- Segment Tree
- Binary Exponentiation