二分法介绍
二分法
- 一、介绍
- 二 、二分法边界
- 1. 一般二分法
- 2. 左边界二分法
- 3. 右边界二分法
- 三、代码实现
- 1、一般二分法
- 2、左边界二分法
- 3、右边界二分法
一、介绍
二分法（Binary Search）是一种常用的查找算法，它的原理是将有序数组分成两部分，通过比较目标值与数组的中间值，可以确定目标值在哪一部分中，然后再继续在目标部分进行查找，直到找到目标值或者确定目标值不存在。
二 、二分法边界
二分法可以分为以下三种情况：
1. 一般二分法
对于有序数组，目标值可能存在也可能不存在。如果找到目标值则返回其索引，否则返回-1。
2. 左边界二分法
对于有序数组，目标值可能存在也可能不存在。如果找到目标值则返回其索引，否则返回比目标值小的最大值的索引。
3. 右边界二分法
对于有序数组，目标值可能存在也可能不存在。如果找到目标值则返回其索引，否则返回比目标值大的最小值的索引。
三、代码实现
1、一般二分法
public int binarySearch(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) {return mid;} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;
}
2、左边界二分法
public int leftBinarySearch(int[] nums, int target) {int left = 0;int right = nums.length;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}return left;
}
3、右边界二分法
public int rightBinarySearch(int[] nums, int target) {int left = 0;int right = nums.length;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) {left = mid + 1;} else {right = mid;}}return left - 1;
}
以上代码中，nums是有序数组，target是目标值。在每一次循环中，通过计算中间值mid来比较目标值与中间值的大小关系，根据比较结果更新left和right的值，直到找到目标值或者确定目标值不存在。
