给一个有序数组和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回 -1
模板四点要素
- 1、初始化：start=0、end=len-1
- 2、循环条件：start <= end
- 3、比较中点和目标值：A[mid] ==、 <、> target
- 4、判断最后两个元素是否符合：A[start]、A[end] ? target
时间复杂度 O(logn)，使用场景一般是有序数组的查找。
// 二分搜索最常用模板
var search = function(nums, target) {
let left = 0, mid = 0, right = nums.length-1;
while(left + 1 < right){
mid = left + ((right-left) >> 1); // 考虑到 start + end 数据溢出的情况
if(nums[mid] === target){
return mid;
}
if(nums[mid] > target){
right = mid - 1;
} else {
left = mid + 1;
}
}
// 最后剩下两个元素，手动判断
if (nums[left] === target) {
return left;
}
if (nums[right] === target) {
return right;
}
return -1;
};大部分二分查找类的题目都可以用这个模板，然后做一点特殊逻辑即可。
模板 #1 (left <= right)
二分查找的最基础和最基本的形式。 查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。 不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。
模板 #2 (left < right)
一种实现二分查找的高级方法。 查找条件需要访问元素的直接右邻居。 使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。 保证查找空间在每一步中至少有 2 个元素。 需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。
模板 #3 (left + 1 < right)
实现二分查找的另一种方法。 搜索条件需要访问元素的直接左右邻居。 使用元素的邻居来确定它是向右还是向左。 保证查找空间在每个步骤中至少有 3 个元素。 需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。
如果是最简单的二分搜索，不需要找第一个、最后一个位置、或者是没有重复元素，可以使用模板#1，代码更简洁：
var search = function(nums, target) {
let start = 0, mid = 0, end = nums.length-1;
while(start <= end){
mid = start + ((end-start)>>1);
if(nums[mid] === target){
return mid;
}
if(nums[mid] > target){
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
};JS 用 indexOf 也可以：
var search = function(nums, target) {
return nums.indexOf(target);
};给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
- 你可以设计并实现时间复杂度为
O(log n)的算法解决此问题吗？
输入：nums = [5,7,7,8,8,10], 输出：[3,4]
var searchRange = function(nums, target) {
if(target<nums[0] || target>nums[nums.length-1]){
return [-1,-1];
}
let res = [-1,-1];
let left = 0, mid = 0, right = nums.length-1;
while(left <= right){
mid = left + ((right-left) >> 1);
if(nums[mid] >= target){
if(mid === 0 || (nums[mid] === target && nums[mid-1]<target)){
res[0] = mid;
break;
}else{
right = mid - 1;
}
}else{
left = mid + 1;
}
}
if(res[0]!==-1 && nums[res[0]]===target){
if(res[0]===nums.length-1){
res[1] = res[0];
} else {
for(let i=res[0]+1;i<nums.length;i++){
if(nums[i] !== target){
res[1] = i-1;
break;
}
if(i===nums.length-1 && nums[i]===target){
res[1] = i;
}
}
}
}
return res;
};var searchRange = function(nums, target) {
return [nums.indexOf(target),nums.lastIndexOf(target)]; //使用内置方法，运行更快
};给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
var searchInsert = function (nums, target) {
let left = 0, mid = 0, right = nums.length - 1
let res = 0
while (left + 1 < right) {
mid = left + ((right - left) >> 1)
if (nums[mid] < target) {
left = mid
} else {
right = mid
}
}
if (target <= nums[left]) {
return left
} else if (target <= nums[right]) {
return right
} else {
return right + 1
}
};编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。
var searchMatrix = function (matrix, target) {
let row = matrix.length
let col = matrix[0].length
let start = 0
let end = row * col - 1
let mid = 0
while (start + 1 < end) {
mid = start + ((end - start) >> 1)
val = matrix[parseInt(mid / col)][mid % col]
if (val > target) {
end = mid
} else if (val < target) {
start = mid
} else {
return true
}
}
if (matrix[parseInt(start / col)][start % col] === target || matrix[parseInt(end / col)][end % col] === target) {
return true
}
return false
};假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
var solution = function (isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function (n) {
let start = 1
let end = n
let mid = 1
while (start + 1 < end) {
mid = start + ((end - start) >> 1)
if(isBadVersion(mid)){
end = mid
} else {
start = mid
}
}
if(isBadVersion(start)){
return start
}
return end
};
};假设按照升序排序的数组在预先未知的某个点上进行了旋转( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。
var findMin = function (nums) {
let start = 0
let end = nums.length - 1
let mid = 0
while (start + 1 < end) {
let mid = start + ((end - start) >> 1)
if (nums[mid] > nums[end]) { // 以最后的为target
start = mid
} else {
end = mid
}
}
if (nums[start] > nums[end]) {
return nums[end]
}
return nums[start]
};给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
var findMin = function (nums) {
let start = 0
let end = nums.length - 1
let mid = 0
while (start + 1 < end) {
while (start < end && nums[start] === nums[start + 1]) {
start++
}
while (start < end && nums[end] === nums[end - 1]) {
end--
}
let mid = start + ((end - start) >> 1)
if (nums[mid] >= nums[end]) {
start = mid
} else {
end = mid
}
}
if(nums[start] > nums[end]){
return nums[end]
}
return nums[start]
};给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
var search = function (nums, target) {
let start = 0
let end = nums.length - 1
let mid = 0
while (start + 1 < end) {
let mid = start + ((end - start) >> 1)
if (nums[mid] === target) {
return mid
}
if (nums[start] < nums[mid]) {
if (nums[start] <= target && target <= nums[mid]) {
end = mid
} else {
start = mid
}
}
if (nums[end] > nums[mid]) {
if (nums[end] >= target && nums[mid] <= target) {
start = mid
} else {
end = mid
}
}
}
if (nums[start] === target) {
return start
} else if (nums[end] === target) {
return end
}
return -1
};同上，数字可重复。
var search = function (nums, target) {
let start = 0
let end = nums.length - 1
let mid = 0
while (start + 1 < end) {
let mid = start + ((end - start) >> 1)
if (nums[mid] === target) {
return true
}
while (start < end && nums[start] === nums[start + 1]) {
start++
}
while (start < end && nums[end] === nums[end - 1]) {
end--
}
if (nums[start] < nums[mid]) {
if (nums[start] <= target && target <= nums[mid]) {
end = mid
} else {
start = mid
}
}
if (nums[end] > nums[mid]) {
if (nums[end] >= target && nums[mid] <= target) {
start = mid
} else {
end = mid
}
}
}
if (nums[start] === target || nums[end] === target) {
return true
}
return false
};二分搜索核心四点要素（必背&理解）
- 1、初始化：start=0、end=len-1
- 2、循环退出条件：start + 1 < end
- 3、比较中点和目标值：A[mid] ==、 <、> target
- 4、判断最后两个元素是否符合：A[start]、A[end] ? target