Binary Search, Easy?
You probably already heard and wrote some pieces of code for binary search already. However, do you really know binary search well enough to handle its many variants? Good for you if your answer is yes, but I would not say someone is a decent software engineer if he/she can not handle it well.
1. The Classic Binary Search:
Find a target value in a sorted array, return its index value in the array if such target exists. Else return -1.
2. The First Occurrence
Given an array and a target number, return the index of the first occurrence of the target in the array or -1 if such target does not exist.
To conclude the trick we used here:
1. Stop when left < right-1
2. Update right/left bound to mid instead of mid-1/mid+1
3. Check both the left and right value in the end to give the optimal result.
3. The last occurrence
Given an array and a target number, return the index of the last occurrence of the target in the array or -1 if such target does not exist.
Could you come up with a solution based on the first occurrence we just solved?
Almost the same trick compare to the first occurrence. The only 2 differences are we consider to go right side of the array first in the while loop and check right pointer before left pointer in the end.
4. Closest Number in Sorted Array
Give an array and a target, find the closest number compare to the target and output its index.
1. Stop when left < right - 1
2. Check absolute difference against target value in the end.
5. K Closest Number in Sorted Array
Give an array and a target, find all the k closest number compare to the target and output all of them as an array.
You may assume that K is always a valid input, that is K < array. length.
Two take away here:
1. We used the binary search technique in the helper function largestSmallerOrEqual
2. Start from that position we expand left or right pointer to get the optimal result. The logic of how we expand the two pointers is worth practicing.
6. Binary Search In a Sorted 2D Array
Search in the sorted matrix, each row of the matrix is sorted in ascending order, and the first element of the row equal to or larger than the last element of the previous row.
return the position if the target is found, otherwise return {-1. -1}.
The trick here is virtually to convert the 2D array into a 1D array by and do the classic binary search.
By: row = mid / cols;
col = mid % cols;
* Bonus 7, find the median of two sorted array
There are two sorted arrays A and B of size m and n respectively.
Find the median of the two sorted arrays. The overall runtime complexity should be O(log (m+n)).
The gist of this question is to realize that the split point i need to satisfy that
1. i + j = ( m + n + 1 ) / 2
2. A[i-1] <= B [j]
3. B[j-1] <= A[i]
We use binary search to find such position i in the first smaller sorted array. Therefore the runtime will be Log(Min( m, n) ).
Next time when you need to solve a binary search related problem, hope you have a better sense -_ -
Enjoy Coding^^
Ye Jiang
No comments:
Post a Comment