1/Jun 2019
3 min. read
In the last binary search article, we discussed how to write a correct binary search. But sometimes we are not asked to find any position of the target. If we need the first or the last occurrence, can we do it?
The classic binary search In Python, the basic binary search looks like this:
lo = 0 hi = N-1 while (lo < hi): mid = (lo+hi)//2 if A[mid] == target: return mid elif A[mid] < target: lo = mid + 1 else: hi = mid return lo if A[lo] == target else -1 And the invariant of the algorithm is that A[lo] <= target <= A[hi].29/Oct 2018
1 min. read
Another exercise from Programming Pearls: Heap. I finished the code a week ago but didn’t have the time for the blog post until now.
Here’s the code:18/Oct 2018
1 min. read
I am reading Programming Pearls and figure it would be fun to write Quicksort in Python.
Here are my code and benchmarks.
When I try to compare my code with others, I am surprised to see many faulty implementations of Quicksort with quadratic runtime on certain input.
The key to write a correct and fast Quicksort:
Watch out for list of equal items. qsort2 uses 2 pointers (i, j) to make sure the problem is divided into subproblems of similar size.12/Dec 2016
5 min. read
Background As I am preparing for interviews recently, this is a good time to write about my experience in writing a binary search. Please correct me if I get anything wrong in the content.
Binary Search Binary search is always one of the most popular algorithms and at the same time tough to implement correctly. It is surprisingly hard to find a correct while easy-to-modify binary search code out there.