Binary Search
Iterative version
while(l<r) {
mid = l + (r - l)/2;
if(target == nums[mid])
return mid;
else if (target > nums[mid])
l = mid + 1;
else
r = mid - 1;
}
Calculation of mid point
mid = (l + r)/2 _or _mid = l + (r - l)/2 is biased to the left.
(the difference is mid = l + (r - l)/2 can avoid number overflow if the index is very large, and have consistent bias when the index could be negative.) We might not be told it could be a test case: 374 Guess Number Higher or Lower
mid = (l + r)/2 + 1 is biased to the right.
Range solution / First occurrence / Last occurrence
Depends on the need, the update of l=mid / r=mid can help us to find range solution, first occurrence or last occurrence.
For example, the crux of below problem is essentially finding the first occurence of an interval, which start point is >= given .end
The distraction of the problem is we have to output the original index, so we can keep a mapping of interval start point -> index.
Once we find such a first occurrence start point, we can lookup the index.
Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.
For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.
Note:
- You may assume the interval's end point is always bigger than its start point.
- You may assume none of these intervals have the same start point.
Example 1:
Input:
[ [3,4], [2,3], [1,2] ]
Output:
[-1, 0, 1]
Explanation:
There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.
Other similar problems:
Binary Search on Value Range or Other Stuff
Binary Search may not be on index of an array, it could be search on a value range:
287. Find the Duplicate Number
it could be search on a possible starting point of something:
Binary Search Tree
Remember BST in-order is very useful! It means the elements are in sorted order. It is useful traversal in solving some problems.
BST in-order ==> Sorted
501. Find Mode in Binary Search Tree
Sorted ==> BST in-order
If we convert the sorted list back to BST, we can just do in-order traversal (when we know the size n) and fill in back the element from the list one by one while we traverse the tree in-order.
109. Convert Sorted List to Binary Search Tree
class Solution {
private ListNode list;
public TreeNode sortedListToBST(ListNode head) {
this.list = head;
int size = 0;
while(head!=null) {
size++;
head = head.next;
}
return buildTree(size);
}
public TreeNode buildTree(int n) {
if (n==0) return null;
TreeNode leftSubTree = buildTree(n/2);
TreeNode root = new TreeNode(list.val);
list = list.next;
TreeNode rightSubTree = buildTree(n-n/2-1);
root.left = leftSubTree;
root.right = rightSubTree;
return root;
}
}