二分搜索
给一个有序数组和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1
模板四点要素
1、初始化：start=0、end=len-1
2、循环退出条件：start + 1 < end
3、比较中点和目标值：A[mid] ==、 <、> target
4、判断最后两个元素是否符合：A[start]、A[end] ? target
时间复杂度 O(logn)，使用场景一般是有序数组的查找
给定一个
n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。
// 二分搜索最常用模板
public int Search(int[] nums, int target)
{
// 1、初始化left、right
int left = 0;
int right = nums.Length - 1;
// 2、处理for循环
while (right - left > 1)
{
int mid = left + (right - left) / 2;
// 3、比较nums[mid]和target值
if (nums[mid] == target)
{
return mid;
}
else if (nums[mid] < target)
{
left = mid;
}
else
{
right = mid;
}
}
// 4、最后剩下两个元素，手动判断
if (nums[left] == target)
{
return left;
}
else if (nums[right] == target)
{
return right;
}
else
{
return -1;
}
}大部分二分查找类的题目都可以用这个模板，然后做一点特殊逻辑即可
另外二分查找还有一些其他模板如下图，大部分场景模板#3 都能解决问题，而且还能找第一次/最后一次出现的位置，应用更加广泛
所以用模板#3 就对了，详细的对比可以这边文章介绍：二分搜索模板
如果是最简单的二分搜索，不需要找第一个、最后一个位置、或者是没有重复元素，可以使用模板#1，代码更简洁
// 无重复元素搜索时，更方便
public int Search_Template(int[] nums, int target)
{
var start = 0;
var end = nums.Length - 1;
while (start <= end)
{
var mid = start + (end - start) / 2;
if (nums[mid] == target)
{
return mid;
}
else if (nums[mid] < target)
{
start = mid + 1;
}
else if (nums[mid] > target)
{
end = mid - 1;
}
}
// 如果找不到，start 是第一个大于target的索引
// 如果在B+树结构里面二分搜索，可以return start
// 这样可以继续向子节点搜索，如：node:=node.Children[start]
return -1;
}给定一个包含
n个整数的排序数组，找出给定目标值target的起始和结束位置。如果目标值不在数组中，则返回
[-1, -1]
思路：核心点就是找第一个 target 的索引，和最后一个 target 的索引，所以用两次二分搜索分别找第一次和最后一次的位置
public int[] SearchRange(int[] nums, int target)
{
if (nums.Length == 0)
{
return new[] { -1, -1 };
}
int mid;
int[] bound = new int[2];
// search for left bound
var start = 0;
var end = nums.Length - 1;
while (start + 1 < end)
{
mid = start + (end - start) / 2;
if (nums[mid] == target)
{
end = mid;
}
else if (nums[mid] < target)
{
start = mid;
}
else
{
end = mid;
}
}
if (nums[start] == target)
{
bound[0] = start;
}
else if (nums[end] == target)
{
bound[0] = end;
}
else
{
bound[0] = bound[1] = -1;
return bound;
}
// search for right bound
start = 0;
end = nums.Length - 1;
while (start + 1 < end)
{
mid = start + (end - start) / 2;
if (nums[mid] == target)
{
start = mid;
}
else if (nums[mid] < target)
{
start = mid;
}
else
{
end = mid;
}
}
if (nums[end] == target)
{
bound[1] = end;
}
else if (nums[start] == target)
{
bound[1] = start;
}
else
{
bound[0] = bound[1] = -1;
return bound;
}
return bound;
}给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
O(log n)的算法。
public int SearchInsert(int[] nums, int target)
{
int low = 0, high = nums.Length - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (nums[mid] == target)
{
return mid;
}
else if (nums[mid] > target)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return low;
}编写一个高效的算法来判断
m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数
target，如果target在矩阵中，返回true；否则，返回false。
public bool SearchMatrix(int[][] matrix, int target)
{
int m = matrix.Length, n = matrix[0].Length;
int low = 0, high = m * n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int row = mid / n, column = mid % n;
if (matrix[row][column] == target) {
return true;
} else if (matrix[row][column] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本
[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用
bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
public int FirstBadVersion(int n, int badVersion)
{
int low = 1, high = n;
while (low < high)
{
int mid = low + (high - low) / 2;
if (IsBadVersion(mid, badVersion))
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}已知一个长度为 n 的数组，预先按照升序排列，经由
1到n次 旋转 后，得到输入数组。例如，原数组nums=[0,1,2,4,5,6,7]在变化后可能得到：
若旋转 4 次，则可以得到
[4,5,6,7,0,1,2]若旋转 7 次，则可以得到
[0,1,2,4,5,6,7]注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。
public int FindMin(int[] nums)
{
int low = 0, high = nums.Length - 1;
while (low < high && nums[low] > nums[high])
{
int mid = low + (high - low) / 2;
if (nums[mid] < nums[low])
{
high = mid;
}
else
{
low = mid + 1;
}
}
return nums[low];
}已知一个长度为 n 的数组，预先按照升序排列，经由
1到n次 旋转 后，得到输入数组。例如，原数组nums=[0,1,4,4,5,6,7]在变化后可能得到：
若旋转 4 次，则可以得到
[4,5,6,7,0,1,4]若旋转 7 次，则可以得到
[0,1,4,4,5,6,7]注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个可能存在 重复 元素值的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须尽可能减少整个过程的操作步骤。
public int FindMin2(int[] nums)
{
int low = 0, high = nums.Length - 1;
while (low < high && nums[low] >= nums[high])
{
int mid = low + (high - low) / 2;
if (nums[low] == nums[mid] && nums[high] == nums[mid])
{
low++;
high--;
}
else if (nums[mid] < nums[low])
{
high = mid;
}
else
{
low = mid + 1;
}
}
return nums[low];
}整数数组
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)的算法解决此问题。
public int SearchRotate(int[] nums, int target)
{
int low = 0, high = nums.Length - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (nums[mid] == target)
{
return mid;
}
if (nums[low] <= nums[mid])
{
if (target >= nums[low] && target < nums[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
else
{
if (target <= nums[high] && target > nums[mid])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
}
return -1;
}注意点
面试时，可以直接画图进行辅助说明，空讲很容易让大家都比较蒙圈
已知存在一个按非降序排列的整数数组
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,4,4,5,6,6,7]在下标5处经旋转后可能变为[4,5,6,6,7,0,1,2,4,4]。给你 旋转后 的数组
nums和一个整数target，请你编写一个函数来判断给定的目标值是否存在于数组中。如果nums中存在这个目标值target，则返回true，否则返回false。你必须尽可能减少整个操作步骤。
public bool SearchRotate2(int[] nums, int target)
{
int low = 0, high = nums.Length - 1;
while (low <= high)
{
int mid = low + (high - low) / 2;
if (nums[mid] == target)
{
return true;
}
if (nums[low] == nums[mid] && nums[high] == nums[mid])
{
low++;
high--;
}
else if (nums[low] <= nums[mid])
{
if (target >= nums[low] && target < nums[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
else
{
if (target <= nums[high] && target > nums[mid])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
}
return false;
}二分搜索核心四点要素（必背&理解）
1、初始化：start=0、end=len-1
2、循环退出条件：start + 1 < end
3、比较中点和目标值：A[mid] ==、 <、> target
4、判断最后两个元素是否符合：A[start]、A[end] ? target
最后更新于