Problem is introduced into
First find the correct binary search code from the following “class binary search” code:
int search(int[] nums,int target){
int low=0,high=nums.length;
while(low < high){
int mid = low + (high-low)/2;
if(nums[mid] < target){
low = mid + 1;
}
else {
high = mid;
}
}
return left;
}
Copy the codeint search(int[] nums,int target){
int low=0,high=nums.length-1;
while(low < high){
int mid = low + (high-low)/2;
if(nums[mid] < target){
low = mid + 1;
}
else {
high = mid;
}
}
return left;
}
Copy the codeint search(int[] nums,int target){
int low=0,high=nums.length;
while(low <= high){
int mid = low + (high-low)/2;
if(nums[mid] < target){
low = mid + 1;
}
else {
high = mid;
}
}
return left;
}
Copy the codeint search(int[] nums,int target){
int low=0,high=nums.length;
while(low < high){
int mid = low + (high-low)/2;
if(nums[mid] <= target){
low = mid + 1;
}
else {
high = mid;
}
}
return left;
}
Copy the code
It feels like tsui jinjiang and Thor, these codes are not similar, they are exactly the same…
Binary search is something that everyone who has studied data structures knows, and the idea is very simple, looking for an element in an ordered array, and because the array is ordered, every time you compare the middle element to the element you’re looking for, you eliminate half of the interval. The overall framework is the same as the above four pieces of code, but the details are too much. For example:
- Is high initialized to nums.length or nums.length-1?
- While is low
- Nums (mids) < target or nums (mids) < = target?
- Low =mid or low=mid+1? High = mid or mid – 1?
- Finally return left or right?
According to the above several conditions arrangement combination, seems to be able to write a dozen looks very similar but do not know the right dichotomous code 😒 dichotomous writing and understanding a lot of methods, not enough, not one said, here gives a dichotomous search writing and understanding methods (only consider the ascending case).
The premise
Binary search, as described in this article, returns a subscript value so that the list is still ordered after the new element is inserted at this location. (Insert is to move all the elements after the insert position back one bit, while the original insert position is assigned to the new element.) This position must exist, but it is not necessarily unique. Given the length of the array NUMs is n, the binary lookup function in this paper returns [0,n].
Binary search for 4 in the array shown below:
From the figure above, we define lower_bound to be the index that is still ordered after the first element is inserted, and upper_bound to be the index that is still ordered after the last element is inserted. So upper_bound is the index of the first element that is greater than or equal to target. In this diagram, lower_bound is 2 and upper_bound is 5.
For example, if you look for 9 in the same array, you can see that all the elements in the array are smaller than 9, so lower_bound is the same as upper_bound, it’s going to be 8, so if you insert 9 at 8, you’re going to keep the array in order.
lower_bound
Direct code
int search(int[] nums,int target){
int low=0,high=nums.length;
while(low < high){
int mid = low + (high-low)/2;
if(nums[mid] < target){
low = mid + 1;
}
else {
high = mid;
}
}
return left;
}
Copy the codeThis is the code that finds lower_bound, which is the first code that is greater than or equal to target. Since target may be larger than all the numbers in the array, high is initialized to nums.length. Let’s look at this part first
if(nums[mid] < target){
low = mid + 1;
}
Copy the codeSince we are looking for the first location that is greater than or equal to target, if nums[mid] < target, then mid and all elements before mid are less than target (nums ascending), that is, to the left of low (0,1….) Mid is all the nonconforming solutions, so let’s just set low = mid + 1, where low is just controlling the nonconforming solutions, and let’s look at the high part
else {
high = mid;
}
Copy the codeIf (nums[mid] >= target) else (nums[mid] >= target); if (mid >= target) else (mid >= target); if (mid >= target) But I don’t know if it’s the first one. Let’s say high equals mid, and high actually represents the possible solutions. Let’s look at the cyclic conditions:
while(low < high)
Copy the codeThis loop terminates when low >= high, and in the context of this article, each round mid is updated to low + (high-low)/2, which is (low + high)/2, and rounded down to prevent overflow, which is a cliche, so I won’t explain it. And then every time low is updated to mid + 1, or high is updated to mid. It’s not hard to prove that in this situation, the end of this cycle must be low == high, there’s no case where low is greater than high. In combination with the above analysis of code updates for low and high, the solution to the left of low is the one that does not meet the condition and can be ignored, while high represents the solution that meets the condition, but it is not known whether it is the first one. So at the end of the loop, low and high are equal, and high is low, which means that everything to the left of high doesn’t fit, and high is the solution that fits, so high is the first solution that fits. In conclusion, low is the solution that does not meet the condition, the elements to the left of low do not meet the condition, and high is the solution that does meet the condition, but not necessarily the first one. Low keeps going to the right, high keeps going to the left, and when low and high overlap, then we have found the first solution that meets the condition.
upper_bound
Nums [mid] <= target (); low [mid] <= target (); high [mid] <= target ()
int search(int[] nums,int target){
int low=0,high=nums.length;
while(low < high){
int mid = low + (high-low)/2;
if(nums[mid] <= target){
low = mid + 1;
}
else {
high = mid;
}
}
return left;
}
Copy the codeChange the low update condition from NUMs [mid] < target to NUMs [mid] <= target. Somebody said, not the low control doesn’t qualify, does the high control qualify? Nums [mid] = nums[mid] =target. Nums [mid] is less than or equal to target, so it must be less than or equal to target. =, nums[mid] is not equal to target, does not mean that the element before it is not equal to target. So you have to be honest about the normal control conditions.
Find where the element appears
Now, the most naive application of binary search, looking for a number in an array, you can call the lower_bound code, because lower_bound is looking for the first number that is greater than or equal to target, so it’s still going to work even if the element is not in the array, and it’s also possible that target is larger than all the numbers in the array, At this point, the code returns the length of the array. So if you look for an element, you just change the lower_bound return value as follows:
if(low == nums.length||nums[low]! =target) return -1; Return low // Otherwise, the array has this element, and the first position that is greater than or equal to target is the first position that is equal to targetCopy the codeSome details
Answer the detailed questions mentioned earlier in this article. These details are written for this article and may not be applicable to other writing methods
- Is high initialized to nums.length or nums.length-1? High is initialized to nums.length, because we’re essentially looking for the insertion position, and it’s possible that target is larger than all the numbers in the array.
- While is low
- Nums (mids) < target or nums (mids) < = target? This is going to vary depending on the problem, but what is the problem, what is the problem
- Low =mid or low=mid+1? High = mid or mid – 1? Low = mid + 1,low controls the ineligible solution, mid is also ineligible; High is mid, because high is controlling the solution that satisfies the condition
- Finally return low or high? Are all the same
So let’s do a couple of problems with that in mind.
Finds the left and right boundaries of the element
Look for the first and last positions of an element in a sorted array given an ascending array of integers, nums, and a target value. Find the start and end positions in the array for the given target value. Return [-1, -1] if there is no target value in the array. Example 1:
Input: nums = [5,7,7,8,8,10], target = 8Copy the codeSo upper_bound-1 and lower_bound.
public int[] searchRange(int[] nums, int target) { if(nums.length==0) return new int[]{-1,-1}; int low=0,high=nums.length; // lower_bound while(low<high){int mid = low + (high-low)/2; if(nums[mid]<target){ low = mid + 1; } else { high = mid; }} //pos1 record lower_bound int pos1 = low; // Reset low and high and go through the next loop looking for upper_bound low=0; high=nums.length; // upper_bound while(low<high){int mid = low + (high-low)/2; if(nums[mid]<=target){ low = mid + 1; } else { high = mid; }} upper_bound if (low== pos1) return new int[]{-1,-1}; return new int[]{pos1,low-1}; }Copy the codeIf target is in the array, then the values of the two numbers are different. If target is not in the array, then the values of the two numbers are different. If target is not in the array, Nums [mid]<=target = nums[mid]<=target = nums[mid]<=target = nums[mid]<=target =target = nums[mid]<=target =target
This code has also been tested on hundreds of use cases by Force buckle officials, so it should be fine.
The first incorrect version
You are a product manager and are currently leading a team to develop a new product. Unfortunately, the latest version of your product does not pass the quality test. Since each version is based on the previous version, all versions after the wrong version are wrong. Suppose you have N versions [1, 2… n] and you want to find the first incorrect version that causes all subsequent versions to fail. You can determine if the version number is wrong in the unit test by calling the bool isBadVersion(Version) interface. Implement a function to find the first incorrect version. You should try to minimize the number of calls to the API. Example 1:
Input: n = 5, bad = 4 Call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true so 4 is the first incorrect version.Copy the codeGo directly to the code:
Public class Solution extends Control {public int firstBadVersion(int n) {public int low =1,high=n; while(low<high){ int mid = low + (high-low)/2; if (! isBadVersion(mid)) { low = mid + 1; } else {high = mid;} else {high = mid; }} return high; // Return high; }}Copy the codeWith the idea introduced in this article, we are looking for the first incorrect version, so when isBadVersion(version) is true, the version at this time is the conforming solution, update high, but not necessarily the first one, so we also need low to control the non-conforming solution. At the end of the loop, low equals high, we’ve found our first solution. It’s easy to code
The code is also tested.
conclusion
This paper gives a writing method of binary search and how to understand it. Of course, there are many ways to write and understand binary search, this article is just one of them. For example, Java’s Arryas.binarySearch
private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
Copy the codeIt’s a little bit different, and you’re interested to see what’s different.