二分查找
1. 基本概念
二分查找也称折半查找，它是一种效率较高的查找方法。
二分查找是计算机科学中最基本、最有用的算之一。它描述了在有序集合中搜索特定值的过程。
二分查找中使用的术语：
- 目标 Target —— 你要查找的值
- 索引 Index —— 你要查找的当前位置
- 左、右指示符 Left、Right —— 我们用来维持查找空间的指标
- 中间指示符 Mid —— 我们用来应用条件来确定我们应该去向左查找哈斯向右查找的索引。
1.1 它是如何工作的？
在最简单的形式中，二分查找对具有指定左索引和右缩影的连续序列进行操作。这就是所有的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。
1.2 识别和模板简介
1.2.1 如何识别二分查找？
如前所述，二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前对其进行排序。
1.2.2 成功的二分查找的3个部分
二分查找一般由三个主要部分组成：
- 预处理 —— 如果集合未排序，则进行排序。
- 二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
- 后处理 —— 在剩余空间中确定可行的候选者
2. 二分查找模板
2.1 模板 I
// 模板#1
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int mid, left = 0, right = nums.length - 1;
while (left <= right) {
mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] > target) right = mid - 1;
else left = mid + 1;
}
return -1;
}
模板#1 是二分查找的最基础和最基本的形式。这是一个标准的二分查找模板。用于查找可以通过访问数组中单个索引来确定的元素或条件。
2.1.1 关键属性
- 二分查找最基础的和最基本的形式。
- 查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
- 不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。
2.1.2 区分语法
- 初始条件：
left = 0，right = length-1 - 终止：
left>right - 向左查找：
right=mid-1 - 向右查找：
left=mid+1
2.2 二分查找模板 II
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int mid, left = 0, right = nums.length;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] > target) right = mid;
else left = mid + 1;
}
if (left != nums.length && nums[left] == target) return left;
return -1;
}
模板#2 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。
2.2.1 关键属性
- 一种实现二分查找的高级方法。
- 查找条件需要访问元素直接右邻居。
- 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
- 保证查找空间在每一步中至少有2个元素。
- 需要进行后处理。当你剩下1个元素时，循环/递归结束。需要评估剩余元素是否符合条件。
2.2.2 区分语法
- 初始条件：
left = 0,right = length - 终止：
left == right - 向左查找：
right = mid - 向右查找：
left = mid+1
2.3 模板 III
public int binarySearch(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int mid, left = 0, right = nums.length;
while (left + 1 < right) {
mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] > target) right = mid;
else left = mid;
}
if (nums[left] == target) return left;
if (nums[right] == target) return right;
return -1;
}
模板#3 是二分查找的另一种独特形式。它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
2.3.1 关键属性
- 实现二分查找的另一种方法。
- 搜索条件需要访问元素的直接左右邻居。
- 使用元素的邻居来确定它是向右还是向左。
- 保证查找空间在每个步骤中至少有3个元素。
- 需要进行后处理。当剩下 2 个元素时，循环/递归结束。需要评估其余元素是否符合条件。
2.3.2 区分语法
- 初始条件：
left = 0，right = length - 1 - 终止：
left + 1 == right - 向左查找：
right = mid - 向右查找：
left = mid
