Finding the left and right boundary is essentially solving the problem that if there are duplicate elements in the array, if there is no target value in the array itself, the two methods will find the same boundary, the first number greater than the target value.
If there are multiple target values, the left boundary is the first to find multiple target values, and the right boundary is the last to find multiple target values.
Look for the right side of the boundary
The target
For example,
Case 1: search for 4 in array [1, 2, 5, 5], then return index 2
Case 2: Array [1, 2, 3, 4, 6, 7, 8] finds 5 and returns index 4
Case 3: Array [1, 2, 3, 3, 5, 6, 7] looks for 3 and returns index 3
Case 4: Looks for 5 in array [1, 2, 5, 5] and returns index 3
The index of the first number in the array greater than target
writing
Binary search
int right_bound(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) {left = mid; } } return right; }Copy the code
Why do you write that?
Just like binary search, you have to pay attention to 1 place
- When the mid pointer is equal to the target element, it locks the right boundary and continues to move the left pointer so that when the left and right Pointers meet, either the first element that is larger than target or the last element that is equal to target
Find a way to write the left edge
The target
For example,
Array [1, 2, 5, 5] find 4, then return index 2
Case 2: Array [1, 2, 3, 4, 6, 7, 8] finds 5 and returns index 4
Case 3: Array [1, 2, 3, 3, 5, 6, 7] looks for 3 and returns index 2
Case 4: Looks for 1 in array [1, 1, 1, 2, 5, 5] and returns index 0
The index of the first number in the array smaller than target
writing
Dichotomy:
int left_bound(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) {right = mid; }} return left; }Copy the code
Why do you write that?
The general writing method and binary search writing method is the same, need to pay attention to 1 place
- When the mid pointer is equal to the target element, the left boundary is locked and the right boundary is moved. The position where the left and right Pointers overlap must be the first target element greater than or equal to target