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

  1. 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

  1. 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