At ordinary times, when we write programs, there are always inexplicable bugs, and after finishing an interface, we are often sprayed by teammates with “what’s the matter with you? The results are inconsistent with expectations.”
Old face a red, and then a person hidden in the corner debugging for a long time, only to find that the original is a certain boundary condition is not handled well, resulting in numerous bugs, today we from binary search algorithm, to talk about how to write the correct program
Binary search algorithms, as we know them, were introduced in 1946, but it wasn’t until 1962 that a completely bug-free binary search algorithm emerged
The idea of binary search method is not complex, many of us can come to the mouth, but why the interval hot yao years, was born completely bug-free binary search algorithm?
Binary search algorithm, difficult in the processing of boundary conditions, we often write a Bug, often also occurs in the processing of boundary conditions
Because learning the idea of an algorithm is very simple, but the idea of landing, writing a completely bug-free binary search, is not an easy thing
So when we write programs, we first need to clear the meaning of the boundary, in the internal implementation of the program, is to maintain the meaning of the boundary
The idea of binary search is briefly repeated here
1. Select target from an ordered array.
2. If the target value is greater than the middle value of the array, then we look in the range below the middle value of the array
3. If the target value is less than the middle value of the array, we look in the range before the middle value of the array
4. Repeat 2,3 steps until the target value is equal to one of the values in the array, and then return the corresponding index position, or there is no target value in the array at all
Okay, that’s the idea of algorithms, so let’s do it. Here I will use the Go language to achieve, to you for more than a month to let you learn the Go language, and you find so many learning materials, there are from small white to advanced Go language video, there are also from small white to Daniel books. If you don’t look at it now, I’m wasting my time
If you want to learn Golang, but don’t have a clue, you can reply “Go” directly in the background of the official account after reading the article, you can get all the learning resources, don’t forget to click back to see it
Put algorithmic ideas on the ground
Let’s define a binary search function MyBinarySearch. It’s called MyBinarySearch because Go has a binary package that contains a function called BinarySearch. We need to distinguish it from it, otherwise the compiler will tell us that we are mucking around (as if saying to me: Are you stupid, there is no need, but to do their own)
func MyBinarySearch(arr []int, target int) (middle int){}Copy the codeWe pass in an array with a target value to query for, and if the target exists in the array, we return its index location
Binary search, easy to problem is the boundary problem, then let’s define first set a boundary, we need to query within the boundary range
// Specify the meaning of the boundary, look for target in [left,right]
left, right := 0.len(arr)- 1
Copy the codeRemember, we’re in a program where every variable is meaningful, and we need to define what each variable is, and our query scope is going to be in [left,right] and we’re going to look at target, and see, what I’ve defined here is a closed interval, which includes the location of the left and right themselves
After defining the meaning of boundary variables, we need to maintain this meaning continuously in the subsequent search process
If the range of the boundary contains valid integers, it means that the boundary is meaningful. So when the boundary has meaning, we loop to determine whether the intermediate value is equal to the target value
for left <= right {
// Look for target in [left,right]
middle = (left + right) / 2 // The index position of the intermediate value
}
Copy the codeSome people here might wonder, why do I use <=? For example, if you close the interval [8,8], then the interval still makes sense because there is an integer 8, and if you remove =, it becomes [8,8], and there are no integers in this interval
Now we need to determine whether the target value is equal to, less than, or greater than the median value in the current query range
If the value is equal, then it’s ok. That’s what we’re looking for. Just return the index position of the intermediate value
if arr[middle] == target {
return
}
Copy the codeSo if it doesn’t, then we have to decide whether we want to be less than the median or more than the median
If the target value is less than the median value, then we need to narrow the range of the query
At this point, the range of our query has changed, and the range on the right side should be shortened to the middle value, which is expressed in Code, that is, right = middle-1
if target < arr[middle] {
// If target < the middle value, we need to look in the left range
right = middle - 1
}
Copy the codeAnd you might ask, why negative 1? Because we already know that target < arr[middle], where middle is, can’t be the position we’re looking for, we need to move it one more bit to the left
Now that you know what left and right mean, when target > arr[middle], our right should also be moved one place to the right of middle
if target > arr[middle] {
// If target > the middle value, then we need to look in the right range
left = middle + 1
}
Copy the codeThe Code above, all pieced together, looks like this. If the target value is not in the array, we return -1
// MyBinarySearch returns the index value of the target element in an ordered array
func MyBinarySearch(arr []int, target int) (middle int) {
left, right := 0.len(arr)- 1 // Specify the meaning of the boundary, look for target in [left,right]
for left <= right {
middle = (left + right) / 2
// If left > right, it means there is no boundary and there is no target value in the array
// So when left <= right, we iterate over the array
if arr[middle] == target {
return
}
if target < arr[middle] {
// If target < the middle value, we need to look in the left range
right = middle - 1
}
if target > arr[middle] {
// If target > the middle value, then we need to look in the right range
left = middle + 1}}return - 1
}
Copy the codeWhen I define the function, I specify the variable name of the return value middle. After declaring the variable name for the return value, the function will initialize the variable to 0 when executing the function, and the corresponding variable name will be automatically specified for the return value
So I didn’t define middle in the function and I just wrote return middle as return
Cyclic invariant
I’m guessing this is the first time many of you have heard of this term, but I’ve emphasized many times above what it means
Now again deliberately explain, carefully read the content of the above you, now I say, you will be able to understand
In our binary search above, we kept going through the loop left <= right, so that’s the loop, and when left <= right, our loop doesn’t end
And what are the invariants? Aren’t left and right variables? How do you say it’s invariant?
The values of left and right change all the time, but their meanings remain the same, because we are always looking for our target value in the closed interval [left,right]
The change in left and right in the program, it’s just narrowing down the closed range, it doesn’t change the meaning of the declaration, notice I said, it doesn’t change the meaning of the declaration
So to write the right program, we need to define the meaning of each variable when we declare it. When a variable changes, we can only change its value, not the meaning of the variable
Once the meaning of its variables is declared, subsequent programs maintain the meaning. Just like each of us is born with meaning, and our life experience, is in order to complete the meaning of life and must have the paving
The reason why we write more bugs is mostly because we do not understand the meaning of variables thoroughly and often declare some meaningless variables (you may think that some variables are not meaningless variables, but most of the time they are).
You think this is it?
Binary search from the proposed to the final bug-free implementation, during the experience of 16 years, to be so simple on the end… I don’t think we’ve been able to get away with it for 16 years
The binary search we implemented above has a hidden Bug: middle = (left +right) / 2
If we sum left and right in this way when the values are large enough, the int type is out of bounds
What if it crosses the line? Remember when we talked about how to sum large integers? Well, if you remember, you’re pretty good, if you solve for the bounds of their median in that way… All I can say is… Are you stupid…
We could have changed middle from addition to subtraction, and we wouldn’t have crossed the line
Middle = left + (right-left) / 2
It’s so cool to be late after all these decades
Write in the last
The weekly algorithm, to be honest, has been stopped for a long time
Today’s post follows the last one, and the interval seems to be several weeks. emmmm
It’s not that I don’t want to keep updating the series, but the fact that you’re not even reading it makes me want to keep writing
If you look closely at my previous weekly algorithms series, you’ll see that none of them are just algorithms. They’re all mixed up with other ideas, or development practices, or some other experience
I don’t think it’s any use to just take the problem on LeetCode and explain it to you, because you can go to Github and read dozens of problems at a time, or you can directly go to LeetCode and read dozens of problems a day. Why do you need to watch me talk…
And finally, just to prove that you’ve mastered the key idea of cyclic invariants, LET me leave you with a question
Left = 0, right = len(arr) -1, right = len(arr) -1
Right = len(arr)-1 = len(arr)-1 = len(arr)-1 = len(arr)-1 = len(arr)-1 = len(arr)-1 = len(arr)-1 = len(arr)-1
The reason I leave you with a question is because it is hard to understand thoroughly without thinking and without seeing
Leave your thoughts in the comments below!
