Binary search algorithm can be said to be a very basic algorithm idea, if written as a problem is generally in the form of:
Given an ordered (ascending) integer array of n elements, nums, and a target value, write a function that searches for the target in NUMs, returning a subindex if the target value exists, or -1 otherwise. Source: Force buckle 704
Don’t look at such a small topic, I also encountered three times in the interview so many times, of course, such a topic is at ease, write down directly, at most two minutes to fix.
Still remember three physics teacher said to me a sentence: “too much confidence, will overturn the boat in the gutter.” At that time, I was very interested in studying physics. Of course, the premise of my interest was that I could always work on the last big problem of physics, and I was always interested in various analyses of mechanics. When the physics teacher says this sentence to me, taking my examination paper to do analysis, answer buckled a few points in addition to calculation error, almost all right, and the choice problem is red brush brush, left knife, right knife, wrong one.
Strives for the square root of x
A few years ago, when I was looking for an internship, I capsized again. One never steps into the same river, but one can capsize twice in the same river. At that time, the interviewer wrote a binary search topic out, I looked at the topic on the heart of a disdain, this question is also out of the test, directly take over, three pen two pen write out, write out the code, long like this:
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1; }}return -1; }}Copy the codeThen the interviewer wrote down another question:
Implement int SQRT (int x) function. Calculates and returns the square root of x, where x is a non-negative integer. Since the return type is an integer, only the integer part of the result is retained, and the fractional part is eliminated. Source: Force-69
And the requirement can not use library functions, how to do this problem, also can not use library functions, is it possible to use addition, subtraction, multiplication and division? This question is not difficult, but I was confused at that time, just like I was walking on stilts on the ice, suddenly the ice broke, I fell into the soft deep water, my mind was blank, I could not think.
In retrospect, the interviewer was very nice. He asked me to pick apples from the tree and offered me a ladder. I told the interviewer, “I don’t need a ladder, you can reach me on stilts.
The stilts did not work as well as the ladder. I fell badly, but the interviewer helped me to stand up and pull me up. With the interviewer’s hints, I managed to do it reluctantly. And the solution used at that time is exactly the routine of binary search.
Here’s the idea!
Suppose that the integral part of the square root of x is a, then a satisfies a∗a≤ XA *a \le XA ∗a≤x, where the lower limit of A is 1 and the upper limit can be roughly thought of as x. If you want to find the number closest to the answer between the lower limit and the upper limit, you can use the dichotomy for successive approximation. The code is as follows.
class Solution {
public int mySqrt(int x) {
if (x == 0)
return 0;
int left = 1, right = x;
while(true) {
int mid = (right - left) / 2 + left;
if (mid > x / mid) {
right = mid - 1;
} else {
if ((mid + 1) > x / (mid + 1)) {
return mid;
}
left = mid + 1; }}}}Copy the codeNote that lines 8 and 11 in the code here cannot be replaced by multiplication, because large numbers can overflow and become negative, resulting in an infinite loop.
From this interview, I dare not despise binary search, this small algorithm, has a great use. There are a lot of problems where you can use the idea of binary search. I also understand a truth, brush is not much, the key is to achieve mastery through a comprehensive study, the thought of society subject, can extrapolate, take binary search, for example, if encounter a similar topic, can think of to solve with binary search, how to solve, if brush algorithm subject, with this ability, is not afraid of a new topic, because the title to the new, the principle is the principle. Here are some examples of using the binary search idea.
The KTH smallest element in the binary search tree
Given a binary search tree, write a function kthSmallest to find the kthSmallest element in it. Note: You can assume that k is always valid and that 1 ≤ k ≤ number of binary search tree elements. Source: Force-230
Binary search tree in order traversal is ordered, this problem can use in order traversal way to do. But here’s a look at how to use the idea of binary search to do this problem.
The structure of a tree is very reminiscent of splitting down the middle, splitting into two. The root element of a binary search tree is the middle of the tree, smaller on the left and larger on the right.
For the binary tree (a) in the graph, the root node of the 15 left subtree of the number of 4, if you want to find small 5, it’s just a root node, if you want to find 3 small, have to go to a left child tree (b) continue to look for, if you want to find small 6, will go to the right sub tree (c) to find, to right subtree (c) in which small? This number is minus the number of left subtrees plus 1, because all the nodes in the right subtree are larger than the root and the left subtree. The code listing is as follows:
class Solution {
public int kthSmallest(TreeNode root, int k) {
int n = count(root.left);
if (k <= n) {
return kthSmallest(root.left, k);
} else if (k > n + 1) {
return kthSmallest(root.right, k - n - 1);
}
return root.val;
}
private int count(TreeNode root) {
if (root == null) {
return 0;
}
return 1+ count(root.left) + count(root.right); }}Copy the codeLooking for repetition
Given an array nums containing n + 1 integers, all of which are between 1 and n (both 1 and N), we know that there is at least one duplicate integer. Suppose there is only one repeating integer, find the repeating number. Example 1: Input: [1,3,4,2,2] Output: 2 Example 2: Input: [3,1,3,4,2] Output: 3 Description: The original array cannot be changed (assuming the array is read-only). You can only use extra O(1). The time complexity is less than O(n2). There is only one repeating number in the array, but it may occur more than once. Source: Force-287
There are several solutions to this problem, but let’s focus on just binary search. To illustrate this approach, let’s look at an example. For the array [1,2,6,4,4,5,3], the repeating element is 4. If you split the array by 4, one is (1,2,3) and the other is (6,4,4,5). Let’s define the function f of x, which is the number of elements in an array that are less than or equal to x
f(1) = 1;
f(2) = 2;
f(3) = 3;
f(4) = 5;
f(5) = 6;
f(6) = 7;
Copy the codeIn other words, if the repeating element in the array is D, there is only one repeating number in the array, but it may be repeated more than once, with the following relationship:
The range of the array is given, and using dichotomy and formulas (1) and (2), you can gradually narrow down the range of repeated elements that are likely to occur. For the array [1,2,6,4,4,5,3], the following uses dichotomy to deduce how to find the repeating elements.
- Left = 1, right = 6, mid = 3, left = 1, right = 6, mid = 3, left = 1, right = 6, mid = 3, left = 1, right = 6, mid = 3, left = 1, right = 6, mid = 3, left = 1, right = 6, mid = 3
- (2) left = 4, right = 6, mid = 5; (3) left = 4, right = 6, mid = 5; (4) left = 4, right = 6, mid = 5;
- (3) left = 4, right = 5, mid = 4; (4) left = 4, right = 5, mid = 4; (5) left = 4, right = 5, mid = 4;
- Step 4: Since left = right, end, answer 4.
If the above procedure is translated into code, it is:
class Solution {
public int findDuplicate(int[] nums) {
int left = 1, right = nums.length - 1;
while (left < right) {
int mid = (right - left) / 2 + left;
int cnt = 0;
for (int v : nums) {
if(v <= mid) { cnt++; }}if (cnt <= mid) {
left = mid + 1;
} else{ right = mid; }}returnleft; }}Copy the codeThere are other questions that use binary search ideas, such as:
- 222. Number of nodes in a complete binary tree
- 35. Search for insertion position
- 153. Find the minimum value in the rotation sort array
- 74. Search for two-dimensional matrices
- 50. Pow(x, n)