二分查找
二分查找主要是通过分治法来实现对数时间复杂度的查找，二分查找的写法很多，但一般可分为三种：相错终止、相等终止、相邻终止。
0. 三个基本模板
模板一 相错终止
int l = 0, r = nums.Length - 1;
while(l <= r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
模板二 相等终止
int l = 0, r = nums.Length;
while(l < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid + 1;
else r = mid;
}
return -1;
模板三 相邻终止
int l = -1, r = nums.Length;
while(l + 1 < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid;
else r = mid;
}
return -1;
二分查找的写法很多，细节也很繁杂，但实际上只要注意下面几个要素就能确定一个二分查找算法的效用。
1. 终止条件是什么？
终止条件即跳出循环的条件，这个一般是由 While 语句的所决定的。
模板一的终止条件是 L = R + 1
模板二的终止条件是 L = R
模板三的终止条件是 L + 1 = R
这是上述三个模板的主要区别，它决定了算法循环结束后 L 和 R 的相对位置。
2. 终止位置有什么意义？
也就是说，我们要确定结束时 L 和 R 位置的元素满足什么条件。以模板一为例：
int l = 0, r = nums.Length - 1;
while(l <= r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
根据循环中的代码，如果找到了 target，那么程序不会跳出循环，而是直接返回。如果没有找到 target，跳出循环时由终止条件即 L = R + 1
并且在循环中，由于 L = mid + 1 以及 R = mid - 1，保证了 L 前面的元素（不包括 L 本身）总是小于 target ，而 R 后面的元素（不包括 R 本身）总是大于 target ，于是我们可以确定如下图的终止情形：
这表明，终止位置的意义是 R 处在最后一个小于 target 的位置，L 处在第一个大于 target 的位置，这两个位置分别称为刚好小于位置和刚好大于位置。
对模板一（模板二、模板三）都可以进行稍加变形，即改变循环中的条件，最终会改变终止位置的意义，从而获得自己想要的信息。比如：
int l = 0, r = nums.Length - 1;
while(l <= r)
{
int mid = l + (r - l) / 2;
if(nums[mid] <= target) l = mid + 1;
else r = mid - 1;
}
终止条件是不变的，依旧是 L = R + 1
注意该代码并不会在找到target的时候直接返回，而是移动 L ，注意 L = mid + 1 保证了 L 前面的元素（不包括 L 本身）总是小于等于 target，由于终止条件是 L = R + 1，我们还要保证该条件有机会成立，因此此处 R = mid - 1，如果写成 R = mid 或者 L = mid 的话是会死循环的，对于相错终止一般总是使用 L = mid + 1 和 R = mid - 1。于是我们得到如下图的终止情形：
这意味着，L 依旧是刚好大于位置，但 R 有两种可能，要么所在元素就是 target，要么就是刚好小于位置。所以跳出循环后，我们需要进一步判断以确定 R 位置的元素。
对于模板二、模板三都是同理的，区别只在于终止条件不同，故最终 L 和 R 的相对位置也不同。
以模板二的一个变形为例：
int l = 0, r = nums.Length;
while(l < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] < target) l = mid + 1;
else r = mid;
}
根据终止条件 L = R 以及循环内的代码，我们可以得到如下图的终止情形：
这时有两种可能，即要么 L/R 所在元素就是 target，要么 L/R 是刚好大于位置。
由于是相等终止，此处使用 L = mid + 1 和 R = mid 是可以保证 L = R 一定有机会成立，同理可以使用 L = mid 和 R = mid - 1。
模板三的分析也一样，区别只是它的终止条件为 L + 1 = R
以模板三的一个变形为例：
int l = -1, r = nums.Length;
while(l + 1 < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] < x) l = mid;
else r = mid;
}
跳出循环后，我们可以得到如下情形：
这个时候 L 为刚好小于位置，而 R 需要进一步判断。在相邻终止的情况下，L = mid 和 R = mid可以保证 L + 1 = R一定有机会成立。
总之，通过代码分析，我们可以确定终止位置的意义，这样根据问题的需要可以自由选择，并且多个模板的多个写法之间存在重合，有些时候都能解决问题。
3. 特殊情况如何处理？
上面所说的都是一般情况下，算法所满足的性质，但有些时候由于数据的特殊性，我们可能会遇到特殊的情况。二分查找要考虑的细节便在这些特殊情况之中。
在上述三个模板中，特殊情况主要是由 L 和 R 的初始值所决定的。对任何一个二分查找算法，我们主要考虑以下几种特殊情况：
- 查找的元素大于数组中所有元素
- 查找的元素小于数组中所有元素
- 数组中仅有一个元素
- 数组中仅有两个元素
基本上三个模板及其变形都会在上面四种情况中的一两种出现问题，事实上，任何简练的模板都不可能兼容所有特殊情况。
这些特殊情况集中在两个问题，第一个问题就是 L 或 R 可能有一个至始至终都未更新，即循环结束时它依旧还是初始值，如果初始值本身就是越界的那么它就有问题了，可能不再具备正确的位置意义。第二个问题就是使用了有关 L 或 R 的下标，但没有考虑到 L 和 R 在特殊情况下会导致下标越界，特别是在数组元素只有一个或两个元素时对下标进行运算的风险很大。
什么情况下 L 或 R 可能有一个不变呢？那就是查找的元素大于或小于所有元素时。
int l = 0, r = nums.Length - 1;
while(l <= r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
对模板一，L 和 R 的初始值都是界内值，如果目标值大于所有元素或者小于所有元素，退出循环时 L = R + 1 = nums.Length 或 L = R + 1 = 0，此时 L 和 R 必定有一个越界了，而另一个依旧会处在刚好大于位置或刚好小于位置。
int l = 0, r = nums.Length;
while(l < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid + 1;
else r = mid;
}
return -1;
对模板二，R 的初始值已经越界，如果目标值大于所有元素，那么退出循环时有 L = R = nums.Length，此时两个都越界了，但依旧能断言 target 不存在。
当然，这里为什么要把 R 的初始值设置为 nums.Length 呢？其实是为了保证程序能够区分出特殊情况，如上所说，如果退出循环时 R = nums.Length，我们可以断言 target 大于所有元素。如果将 R 的初始值设置为 R = nums.Length - 1，那么如果退出循环时 R = nums.Length - 1，我们无法确定是因为 target 大于所有元素还是最后一个元素就是 target。
int l = -1, r = nums.Length;
while(l + 1 < r)
{
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) l = mid;
else r = mid;
}
对于模板三，L 和 R 的初始值均越界，存在 L + 1 = R = nums.Length 以及 L + 1 = R = 0 两种情况，此时必定有一个越界了，而另一个依旧会给出正确的位置意义。
上面只是列举了三个模板最简单的越界情况，对于三个模板的变形（循环体内改为大于、大于等于、小于、小于等于），各自会有其越界情形。面对一个具体问题时，我们最好对可能的特殊情况都进行验证，这是最笨的办法，却也是最高效的。
4. 如何选择使用哪个模板？
实际上考虑每个模板的变形在内，很多问题都可以使用多个模板来解决，因为它们都能表达相同的逻辑，区别只在于退出时 L 和 R 位置意义和特殊情况的不同。关键是对问题和代码的分析，之后也只是看个人习惯而已。
查找元素的第一个和最后一个位置
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target，返回 [-1, -1]。
本题要查找target第一次出现的位置和最后一次出现的位置，使用两次二分查找即可。以相错终止为例，为了查找第一次出现的位置，可用如下模式，结束时 L - 1 如果有效（不越界，且nums[L - 1] == target）即target最后一次出现的位置。
if(nums[mid] <= target) l = mid + 1; else r = mid - 1;
为了查找最后一次出现的位置，可用如下模式，结束时 R + 1 如果有效（不越界，且nums[L - 1] == target）即target第一次出现的位置。
if(nums[mid] < target) l = mid + 1; else r = mid - 1;
搜索旋转排序数组
LeetCode 33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值互不相同 。在传递给函数之前，nums在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
此题预先对数组进行了旋转，并非全局有序，但旋转后总是具有局部有序性质：对一个旋转后的有序数组，在任何位置将数组分割为两部分，必定有一部分是有序的（约定空的子数组和单个元素的子数组是有序的）。
有了这个性质，我们可以对有序的部分进行二分查找，由于数组中的值互不相同，因此目标target只能存在于分割后的某个部分，如果target存在于有序的部分，对该部分进行二分查找即可，如果target存在于另一部分，对该部分继续分割即可。
本题展示了二分查找隐含的递归性质，虽然二分查找是迭代算法，但对每一个区间 [L, R] 的处理方式都是相同的，对一个较大的区间的处理可以影响后续对其子区间的处理，同样对子区间的处理同样会影响子区间的子区间的处理，而所有区间的处理代码都是相同的，这体现了递归性质。
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int l = 0, r = n - 1;
while(l <= r) {
int mid = l + (r - l) / 2;
if(nums[mid] == target) return mid; //如果已经找到直接返回
else if(nums[0] <= nums[mid]) { //判断第一部分是否有序
if(nums[0] <= target && target < nums[mid]) {
r = mid - 1; //如果第一部分有序且target位于该部分，对该部分二分查找即可。
} else {
l = mid + 1; //如果第一部分有序且target不位于该部分，对另一部分继续分割即可。
}
} else { //第二部分有序，下同
if(nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
}
有序数组中的缺失元素
LeetCode 1060. 有序数组中的缺失元素
现有一个按升序排列的整数数组nums，其中每个数字都互不相同 。
给你一个整数k，请你找出并返回从数组最左边开始的第k个缺失数字。
本题有一个\(O(n)\)时间复杂度的简单解法，直接遍历并记录缺失数的数量，直到第k个为止。为了实现\(O(logn)\)时间复杂度，可以使用二分查找。关键是要确定二分查找的序列对象，该序列必须是有序的，显然本题的序列对象不可能是nums。
由于nums是升序的，对于索引i和索引j，如果它们之间不缺少任何数字，必须满足\(nums[j] - nums[i] == j - i\)，如果缺少数字，缺失数的数量为\(nums[j] - nums[i] + 1 - (j - i + 1)\)。计算两个索引之间的缺失数的数量的时间复杂度是常数级别的，可以以缺失数的数量为序列对象，但还需保证该序列有序，因此可以取索引0和索引i之间的缺失数的数量\(missing[i] = nums[j] - nums[0] + 1 - (j - 0 + 1)\)，显然该序列是升序的。
为了确定第k个缺失数，找到满足\(missing[i - 1] < k <= missing[i]\)的索引i，则第k个缺失数为\(nums[i - 1] + (k - missing[i - 1])\)，这相当于查找缺失数序列中第一个大于等于k的元素，即刚好大于位置，因此可以使用如下方式：
if(midv < k) { l = mid + 1; } else { r = mid - 1; }
在相错终止下，循环结束后 R 刚好位于第一个大于等于k的元素。
class Solution {
private int missing(int[] nums, int i) {
return nums[i] - nums[0] + 1 - (i - 0 + 1);
}
public int missingElement(int[] nums, int k) {
int n = nums.length;
int l = 0, r = n - 1;
int m = missing(nums, n - 1);
if(k > m) return nums[n - 1] + (k - m);
while(l <= r) {
int mid = l + (r - l) / 2;
int midv = missing(nums, mid);
if(midv < k) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return nums[r] + (k - missing(nums, r));
}
}
最长重复子串
给你一个字符串s，考虑其所有重复子串 ：即s的（连续）子串，在s中出现 2 次或更多次。这些出现之间可能存在重叠。返回任意一个可能具有最长长度的重复子串。如果s不含重复子串，那么答案为 "" 。
这是一道Hard题，注意题意允许重复子串重叠，并要求该子串至少重复2次，因此可能的最长长度为n - 1。\(O(n^2)\)的思路是显然的：为了得到最长的重复子串，我们从长度为n - 1进行尝试，看看是否存在至少重复2次的子串，可以使用哈希表来记录，由于题目只是要求返回任意一个可能具有最长长度的重复子串，因此只要搜索到一个满足的子串就可以作为答案了。
可以使用二分查找将对长度的遍历降低到\(O(logn)\)时间复杂度，这是因为长度是天然有序的，二分查找的时候优先查找较长的部分即可定位到最长长度。
上述过程假设了对子串的遍历是\(O(n)\)时间复杂度，遍历包括两个过程：遍历每个起始位置以及判断子串是否重复，前者必然是O(n)的，因此要保证后者是O(1)的，但默认的哈希表是通过hashCode来实现的，而对字符串取hashCode必须遍历一次字符串，因此时间复杂度提高了，此时需要使用滑动哈希。
滑动哈希的原理是实现一个滑动窗口，并在滑动的过程中以O(1)的时间复杂度计算窗口内子串的哈希值，这需要一种动态计算哈希的方式，在增加字符和删除字符的时候更新哈希值。设子串[i..j]（包括字符i和字符j）的哈希值为H[i, j]，先考虑H[0, i]：
\( H[0, i + 1] = H[0, i] * PRIME + S[i + 1] \)
其中PRIME是一个素数，Java的hashCode实现中取了31，实际上可以取31、313、3131、...或者13、131、1313、...，而S[i + 1]代表索引i + 1处的字符。特别地，H[i, i] = S[i]。同理有
\( H[i, j + 1] = H[i, j] * PRIME + S[j + 1] \)
\( H[i + 1, j] = H[i, j] - S[i] * PRIME ^ {j - i} \)
接下来考虑删除字符的时候，如何更新哈希值，即如何从H[i, j]推导出H[i + 1, j + 1]：
\( H[i + 1, j + 1] = S[i + 1] * PRIME ^ {j - i} + S[i] * PRIME ^ {j - i + 1} + ... + S[j] * PRIME + S[j + 1] \)
\( = H[i, j] * PRIME + S[j + 1] - S[i] * PRIME ^ {j - i + 1} \)
对于一个定长（LEN）的子串而言，有：
\( H[i + 1, i + LEN] = H[i, i + LEN - 1] * PRIME + S[i + LEN] - S[i] * PRIME ^ {LEN} \)
这样就可以使用滑动窗口计算了，有：
\( H[L + 1, R + 1] = H[L, R] * PRIME + S[R + 1] - S[L] * PRIME ^ {LEN} \)
其中\( PRIME ^ {LEN} \) 是固定的，可以提前算出。
class Solution {
public String longestDupSubstring(String s) {
String ans = "";
int l = 0, r = s.length() - 1;
while (l <= r) {
int mid = (l + r + 1) / 2;
String x = find(s, mid);
if (!x.equals("")) {
l = mid + 1;
ans = x;
} else {
r = mid - 1;
}
}
return ans;
}
private String find(String s, int len) {
Map<Long, Integer> map = new HashMap<Long, Integer>();
long prime = 313;
long hash = 0, power = 1;
int left = 0;
int right = left + len - 1;
for(int i = left; i <= right; i++) {
hash = hash * prime + s.charAt(i);
power *= prime;
}
map.put(hash, 0);
while(right <= s.length() - 1) {
if (map.containsKey(hash) && map.get(hash) != left) {
return s.substring(left, right + 1);
}
map.put(hash, left);
right++;
if(right >= s.length()) break;
hash = hash * prime + s.charAt(right)
- power * s.charAt(left);
left++;
}
return "";
}
}