Overview
The binary search method is a simple algorithm derived from mathematical ideas.
It is the simplest intermediate algorithm. Because many people who are not computer professionals know and are exposed to dichotomy to some extent, dichotomy is often used by some companies as a comprehensive quality question to test the IQ and numerical sensitivity of applicants.
Binary search algorithm questions usually have obvious hints. When an ordered array or O(logN) time complexity requirement appears in the question, binary search will be the first choice.
At the same time, the question will also emphasize that there are no duplicate elements in the array, because once there are duplicate elements, the element index returned by the binary search method may not be unique. These are the prerequisites for using the binary search method.
Mathematical Logic of Binary Search
- Based on the indices of the left and right endpoints, the value of the midpoint can be found in O(1) time.
- Under the premise that the array is ordered, comparing the midpoints can directly eliminate half of the possibilities.
- Therefore, the O(N) search is simplified to O(log2N) elimination.
Loop Invariant- Open/Closed Interval ⭐️
Binary search involves various boundary conditions.Although the logic is relatively simple, it is difficult to write. For example, whether should we write "while (left < right)" or "while (left < = right)"? Moreover, whether should we write "right = middle" or "right = middle - 1"?
The real problem is that the developers might not have thought clearly about the definition of interval. The definition of interval is an invariant. To maintain the invariant in the binary search process, every boundary processing in the while loop must be operated according to the definition of interval. This is the loop invariant rule.
There are two kinds of intervals in writing binary search: left closed and right closed, i.e. [left, right], or left closed and right open, i.e.[left, right)。My personal habit is to use [left, right]. You can refer to the following template:
left, right = 0, len(nums) -1 while ( left <= right ): mid = (left + right) >> 1 if ( nums[mid] == target ) : return ret if (nums[mid] > target): right = mid - 1 else: left = mid + 1 return err
Problem Set and Analysis
Binary search is a classic algorithm in array search problems, so you can see that most of the classic binary search questions and algorithms are at the top of the Leetcode problem set.
Although the binary search algorithm is relatively straightforward, the difficulty of binary search questions is relatively flexible. The pure and most basic binary search can be asked on its own, and it is also a typical simple question. Later, as the conditions of the array begin to become more abstract, the difficulty of the questions will also increase.
| ID | Problem | Diff | Binary Search Strategy |
|---|---|---|---|
| 704 | Binary Search | Easy | The most basic binary search. |
| 35 | Search Insert Position | Easy | The most basic binary search. |
| 74 | Search a 2D Matrix | Medium |
Difficulty: transform the 2D Array into 3D But there is no difference. You can first use the row-first idea to determine which row the target will appear in, and then use a normal binary search to take it away. |
| 34 | Find First and Last Position of Element in Sorted Array | Medium |
Difficulty: Elements are repeated, the answer is likely not unique The binary search process is still the same, but the nums[mid]==target block no longer directly returns the result. Instead, it needs to traverse [left, right] (you can also use left and right clamping) to determine the final [start, end]. |
| 33 | Search in Rotated Sorted Array | Medium |
Difficulty: Arrays are not Unconditionally Ordered During the search, we need to process a rotation axis point. We need to process the arrays [l, r] and [l, p, r] respectively. The middle point p represents the point where the maximum value suddenly drops to the minimum value. However, the breakthrough point is that after rotation, nums[0] must be greater than nums[-1]. This can be used to determine the search direction. |
| 153 | Find Minimum in Rotated Sorted Array | Medium |
The difficulty and solution are the same as those of question 33. However, you need to return the minimum value, which is the rotation axis point in question 33. During the search process, the mid element is constantly compared with the right border, and there will be three situations:
|
| 4 | Median of Two Sorted Arrays | Hard |
Primary Idea: To find the k-th (k>1) smallest element, so we can compare pivot1 = nums1[k//2-1] with pivot2 = nums2[k//2-1] There are k/2-1 elements in nums1 that is smaller or equal to pivot1: nums1[0 .. k/2-2] There are k/2-1 elements in nums2 that is smaller or equal to pivot2: nums2[0 .. k/2-2] Takes pivot = min(pivot1, pivot2), the number of elemnts in the two arraies that are smaller or equal to pivot will not exceed (k/2-1) + (k/2-1) <= k-2 In this way, the pivot itself can only be the k-1th smallest element at most. If pivot = pivot1, then nums1[0 .. k/2-1] can never be the k-th smallest element. "Delete" all these elements and use the remaining elements as the new nums1 array If pivot = pivot2, then nums2[0 .. k/2-1] can never be the k-th smallest element. "Delete" all these elements and use the remaining elements as the new nums2 array Since we "deleted" some elements (these elements are smaller than the k-th smallest element), we need to modify the value of k by subtracting the number of deleted elements. |