本文主要是介绍一个月速刷leetcodeHOT100 day14 彻底搞懂二分搜索 以及相关题目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
二分查找算法（Binary Search Algorithm）
是一种用于在已排序数组中查找特定元素的高效算法。它的基本思想是每次将待查找的区间分成两部分，并确定目标元素位于哪一部分中，然后只在目标区间中继续查找，直到找到目标元素或者确定目标元素不存在。
基本实现
function BinarySearch(nums, target) {let [left, right] = [0, nums.length - 1];while (left <= right) {let mid = left + Math.floor((right - left) / 2);if (target === nums[mid]) {return mid;} else if (target > nums[mid]) {left = mid + 1;} else {right = mid - 1;}}return -1;}
二、寻找左/右侧边界的二分搜索
一个数组[1,2,2,2,3,4]查找2
function left_bound(nums,target) {let [left, right] = [0, nums.length - 1];// 搜索区间为 [left, right]while (left <= right) {let mid = left + (right - left) / 2;if (nums[mid] < target) {// 搜索区间变为 [mid+1, right]left = mid + 1;} else if (nums[mid] > target) {// 搜索区间变为 [left, mid-1]right = mid - 1;} else if (nums[mid] === target) {// 收缩右侧边界right = mid - 1;
// 收缩左侧边界
//left = mid + 1
}}return left;}
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
var searchInsert = function(nums, target) {
j j
if(nums.length==1) return nums[0]>=target?0:1;let start=0, end =nums.length;if(target<=nums[0]) return 0;let mid = 0;while(start<=end) {mid=parseInt((start+end)/2);if(nums[mid]==target) return mid;else if(nums[mid]>target) {end = mid-1;if(target>nums[end]) return mid;}else {start = mid+1;if(target<=nums[start]) return start;}}return nums.length;};
搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
**输入：**matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
**输出：**true
示例 2：
**输入：**matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
**输出：**false
var searchMatrix = function(matrix, target) {let m = matrix.length;let n = matrix[0].length;let low = 0;let high = m*n-1;while(low <= high) {
// `>>` 是 JavaScript 中的位右移运算符，它将一个数字的二进制表示向右移动指定的位数。在这个上下文中，`high - low` 表示了索引范围的大小，将其右移一位，相当于将范围大小除以2。
//let mid = low + (hight -low) / 2
let mid = low +((high - low) >> 1);
//一维索引 `mid` 除以列数 `n`，得到的结果表示 `mid` 所在的行数
//用得到的行索引和列索引来访问二维矩阵中的特定元素
let value = matrix[Math.floor(mid/n)][mid%n]if( value < target){low = mid + 1;} else if(value > target) {high = mid -1;}else {return true;}}return false;};
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
**输入：**nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
**输入：**nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
**输入：**nums = [], target = 0
输出：[-1,-1]
思路:两次while循环 寻找左边界和右边界或找到值后左右查找
var searchRange = function(nums, target) {let result = [-1, -1];let len = nums.length;if (len === 0) return result;// 寻找左边界 let l = 0, r = len - 1;while (l < r) {let mid = (l + r) / 2 | 0;if (target <= nums[mid]) r = mid;else l = mid + 1}if (nums[l] !== target) return result;result[0] = l;r = len - 1;while(l < r) {let mid = (l + r) / 2 | 0;if (target >= nums[mid]) l = mid + 1else r = mid;}if (nums[r] === target) result[1] = relse result[1] = r - 1return result;
};//2.
var searchRange = function(nums, target) {let left = 0, right = nums.length - 1, mid;while (left <= right) {mid = (left + right) >> 1;if (nums[mid] === target) break;if (nums[mid] > target) right = mid - 1;else left = mid + 1;}if(left > right) return [-1, -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,5,6,7] 在下标 3 处经K旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
**输入：**nums = [4,5,6,7,0,1,2], target = 0
**输出：**4
示例 2：
**输入：**nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
**输入：**nums = [1], target = 0
输出：-1
这最简单的办法直接indexOf就行 可这是二分查找的题
var search = function(nums, target) {
return nums.indexOf(target)
};
var serch = function(nums,target){
let left = 0let right = nums.length - 1while(left <= right) {let mid = (left + right) >> 1if(nums[mid] == target) return mid// 如果中间数小于最右边数，则右半段是有序的// 如果中间数大于最右边数，则左半段是有序的if(nums[mid] < nums[right]) {if(target <= nums[right] && target > nums[mid]) {//如果在，则中间数右移leftleft = mid + 1} else {right = mid - 1}} else {if(target < nums[mid] && target >= nums[left]) {right = mid - 1} else {left = mid + 1}}}return -1
}}
寻找旋转排序数组中的最小值
已知一个长度为 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) 的算法解决此问题。
示例 1：
**输入：**nums = [3,4,5,1,2]
**输出：**1
**解释：**原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
**输入：**nums = [4,5,6,7,0,1,2]
**输出：**0
**解释：**原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。
示例 3：
**输入：**nums = [11,13,15,17]
**输出：**11
**解释：**原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
思路：简单做法排序后直接shift，如果通过二分法， 判断 nums[mid] 与 nums[right] 的大小关系： 如果 nums[mid] > nums[right]，说明最小元素在 mid 的右侧，因此更新 left = mid + 1。 否则，最小元素在 mid 或者 mid 的左侧，因此更新 right = mid。 当 left 和 right 相遇时，循环结束，此时 left 指向的位置就是最小元素的位置。
var findMin = function(nums) {
return nums.sort((a,b)=>a-b).shift()
};
var findMin = function (nums) {
let [left,right]= [0,nums.length -1]while (left < right) {const mid = (right + left) >> 1if (nums[mid] > nums[right]) {left = mid + 1} else {right = mid}}return nums[left]};这篇关于一个月速刷leetcodeHOT100 day14 彻底搞懂二分搜索 以及相关题目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
