As a very efficient search algorithm, binary search is worth learning and mastering.
First of all, binary search is based on a sort array or an array changed by certain rules, which is the premise of binary search.
Ordinary binary search, such as finding a number in the sorting array, the algorithm constantly reduces the range to be searched by twice, so the efficiency of search is improved to O(long n)
Example ordinary binary search
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // Be careful
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // Be careful
else if (nums[mid] > target)
right = mid - 1; // Be careful
}
return -1;
}
- The operation of an array must first ensure that it cannot cross the boundary. This is a big taboo of coding. Generally, it is better to use right=length-1. Because of some special requirements, we should also compare the subscripts as mid, left and right. If we use right=length, it will cross the boundary.
- Next, we are concerned about whether the while judgment is < or < = if < is used, the loop will exit when left=right. If left < = right is used, the loop will not exit when left=right is used. Run it again. Imagine if there is left =mid+1 in the loop body; The operation of has already reached its goal. If it can't be adjusted properly, it can cross the boundary or run overtime. In general, we should decide whether to use < = according to the example of drawing by ourselves.
- I don't want to draw a picture to demonstrate the above simple, I believe that everyone will. Next, I will take you through two examples to understand the details of binary search algorithm.
To move the first elements of an array to the end of the array, we call it the rotation of the array.
Input a rotation of a non decrementing array, and output the minimum elements of the rotation array.
For example, array {3,4,5,1,2} is a rotation of {1,2,3,4,5} and the minimum value of the array is 1.
NOTE: all the given elements are greater than 0. If the array size is 0, please return 0.
This problem also can use dichotomy search, how to solve a problem that can't see the answer at a glance, then look twice?. We should take out the paper and pen, draw specific examples, and simulate the machine with our brains. (experts don't need it, and they won't search for it in two points.).
Don't talk much. Look at the picture.
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int length = rotateArray.size();
if (length == 0)
return 0;
int left = 0;
int right = length - 1;
while (left < right)
{
int mid = (left + right) / 2;
if (left == mid)
{
return rotateArray[left + 1];
}
if ((rotateArray[left] >= rotateArray[mid]) && (rotateArray[right] >= rotateArray[mid]))
{
right = mid;
continue;
}
if ((rotateArray[left] <= rotateArray[mid]) && (rotateArray[right] <= rotateArray[mid]))
{
left = mid;
continue;
}
}
return 0;
}
};I find that in fact, the code is piled up with examples. No one can take all the situations into consideration at once. The key is to write frequently, not just think about it, but easily get dizzy.
Case 2, Find the first and last position of an element in a sort array
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Given an ascending array of integers, nums, and a target value, target. Find the start and end position of the given target value in the array.
Your algorithm time complexity must be O(log n) level.
Returns [- 1, - 1] if the target value does not exist in the array.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [- 1, - 1]
This problem is also an upgrade of binary search, right above.
In other words, you should use specific examples to stack up the code, rather than use the code to test the examples. The solution of the above examples is not unique. For example, you can also include the target value in the interval, just draw a picture and stack the code according to your rules.
The difference between < and < = mentioned above, in our problem, we must exit when = = because we want to use the left value at the same time. So how to use it has to be analyzed by yourself.
class Solution {
public:
int leftfind(vector<int>& nums, int target)
{
int length = nums.size();
if (length==0)
{
return -1;
}
int left = 0;
int right = length;
while (left < right)//It will jump out when left=right. The left bit is not detected
{
int mid = (left + right) / 2;
if (nums[mid] == target)
{
right = mid;
}
else if (nums[mid] > target)
{
right = mid;
}
else if (nums[mid] < target)
{
left = mid + 1;
}
}
if (left==length)
{
return -1;
}
return nums[left] == target ? left : -1;
}
int rightfind(vector<int>& nums, int target)
{
int length = nums.size();
if (length == 0)
{
return -1;
}
int left = 0;
int right = length;
while (left < right)//Left open and right closed
{
int mid = (left + right) / 2;
if (nums[mid] == target)
{
left = mid + 1;//Drive to the right.
}
else if (nums[mid] < target)
{
left = mid + 1;
}
else if (nums[mid] > target)
{
right = mid;
}
}
if (left == 0)
{
return -1;
}
return nums[left - 1] == target ? left - 1 : -1;
}
vector<int> searchRange(vector<int>& nums, int target)
{
//Binary search, left boundary
int left = leftfind(nums, target);
int right = rightfind(nums, target);
vector<int> ret;
if ((left==-1) ||(right==-1))
{
ret.push_back(-1);
ret.push_back(-1);
}
else
{
ret.push_back(left);
ret.push_back(right);
}
return ret;
}
};
