Javascript算法——二分查找

1.数组

1.1二分查找

1.搜索索引

开闭matters！！！[left,right]与[left,right)

/*** @param {number[]} nums* @param {number} target* @return {number}*/
var search = function(nums, target) {let left=0;let right=nums.length-1;//[left,right]，相等时能取到，有意义while(left<=right){let mid =Math.floor((left+right)/2);if(target===nums[mid]){return mid;}else if (target>nums[mid]) {left=mid+1;}else{right=mid-1;}}return -1;};
console.log(search([-1,0,3,5,9,12],2))//-1
console.log(search([-1,0,3,5,9,12],2))//4

/*** @param {number[]} nums* @param {number} target* @return {number}*/
var search = function(nums, target) {// right是数组最后一个数的下标+1，nums[right]不在查找范围内，是左闭右开区间let mid, left = 0, right = nums.length;    // 当left=right时，由于nums[right]不在查找范围，所以不必包括此情况while (left < right) {// 位运算 + 防止大数溢出mid = left + ((right - left) >> 1);// 如果中间值大于目标值，中间值不应在下次查找的范围内，但中间值的前一个值应在；// 由于right本来就不在查找范围内，所以将右边界更新为中间值，如果更新右边界为mid-1则将中间值的前一个值也踢出了下次寻找范围if (nums[mid] > target) {right = mid;  // 去左区间寻找} else if (nums[mid] < target) {left = mid + 1;   // 去右区间寻找} else {return mid;}}return -1;
};

2.搜索插入位置

/*** @param {number[]} nums* @param {number} target* @return {number}*/
var searchInsert = function(nums, target) {let left=0;let right=nums.length-1;//[left,right]，相等时能取到，有意义while(left<=right){let mid =Math.floor((left+right)/2);if(target===nums[mid]){return mid;}else if (target>nums[mid]) {left=mid+1;}else{right=mid-1;}}// 分别处理如下四种情况// 目标值在数组所有元素之前  [0, -1]// 目标值等于数组中某一个元素  return middle;// 目标值插入数组中的位置 [left, right]，return  right + 1// 目标值在数组所有元素之后的情况 [left, right]，这是右闭区间，所以  return right + 1return right+1;};
console.log(search([1,3,5,6],0))//0
console.log(search([1,3,5,6],3))//1
console.log(search([1,3,5,6],4))//2
console.log(search([1,3,5,6],7))//4

其余三种都可以归纳为right+1

3.在排序数组中查找元素的第一个和最后一个位置

找左边界时，需将right赋给左边界，所以在target<=num[mid]时更新right并更新左边界
找右边界时，需将left赋给右边界，所以在target>=num[mid]时更新left并更新右边界
情况二，通过rightBorder-leftBorder>1条件判断

var searchRange = function(nums, target) {const getLeftBorder = (nums, target) => {let left = 0, right = nums.length - 1;let leftBorder = -2;// 记录一下leftBorder没有被赋值的情况while(left <= right){let middle = left + ((right - left) >> 1);if(nums[middle] >= target){ // 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else {left = middle + 1;}}return leftBorder;}const getRightBorder = (nums, target) => {let left = 0, right = nums.length - 1;let rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {let middle = left + ((right - left) >> 1);if (nums[middle] > target) {right = middle - 1;} else { // 寻找右边界，nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;}}return rightBorder;}let leftBorder = getLeftBorder(nums, target);let rightBorder = getRightBorder(nums, target);// 情况一if(leftBorder === -2 || rightBorder === -2) return [-1,-1];// 情况三if (rightBorder - leftBorder > 1) return [leftBorder + 1, rightBorder - 1];// 情况二return [-1, -1];
};

4.X的平方根

function mySqrt(x) {  if (x === 0) return 0; // 特殊情况处理：0的平方根是0  let left = 1; // 搜索范围的左边界  let right = Math.floor(x / 2) + 1; // 搜索范围的右边界，x/2是一个合理的上限，因为平方根不会超过x/2（对于非负整数x）  while (left <= right) {  let mid = Math.floor((left + right) / 2); // 计算中间值  let square = mid * mid; // 计算中间值的平方  if (square === x) {  return mid; // 如果平方正好等于x，直接返回  } else if (square < x) {  left = mid + 1; // 如果平方小于x，说明平方根在mid的右侧，移动左边界  } else {  right = mid - 1; // 如果平方大于x，说明平方根在mid的左侧或正好是mid（但我们需要整数部分，所以向左移动）  }  }  // 循环结束时，left会指向比实际平方根大的最小整数，而right会指向比实际平方根小的最大整数  // 因为我们需要整数部分，所以返回right（它是最后一个使得mid*mid <= x的mid值）  return right;  
}  // 测试  
console.log(mySqrt(4));  // 输出: 2  
console.log(mySqrt(8));  // 输出: 2 (8的平方根约为2.8284，取整数部分2)  
console.log(mySqrt(15)); // 输出: 3 (15的平方根约为3.8729，取整数部分3)

解释

边界条件：
如果 x 为0，则直接返回0。
搜索范围：
左边界 left 初始化为1，因为0的平方根是0（已经特殊处理），而任何正数的平方根至少为1。
右边界 right 初始化为 Math.floor(x/2)+1，因为平方根不会超过 x/2（对于非负整数 x）。加1是为了确保在 x 为完全平方数时能够包含这个平方根。
二分查找：
在每次迭代中，计算中间值 mid 及其平方 square。
根据 square 与 x 的比较结果，移动左边界或右边界。
返回结果：
循环结束时，返回 right，它是最后一个使得 mid * mid <= x 的 mid 值，也就是我们要找的平方根的整数部分。

这种方法的时间复杂度是 O(logn)，其中 n 是 x 的值，因为每次迭代都会将搜索范围减半。

更精确 (待进一步补充）

function mySqrt(x) {  if (x === 0) return 0; // 特殊情况处理：0的平方根是0  let guess = x; // 初始猜测值设为x本身（对于非负整数，平方根不会超过x本身）  let epsilon = 1; // 精度控制，用于判断迭代是否结束  while (Math.abs(guess * guess - x) >= epsilon) {  // 牛顿迭代公式：guess = (guess + x / guess) / 2  guess = Math.floor((guess + Math.floor(x / guess)) / 2);  // 为了确保精度，逐步减小epsilon  epsilon /= 10;  }  return guess;  
}  // 测试  
console.log(mySqrt(4));  // 输出: 2  
console.log(mySqrt(8));  // 输出: 2 (8的平方根约为2.8284，取整数部分2)  
console.log(mySqrt(15)); // 输出: 3 (15的平方根约为3.8729，取整数部分3)

初始猜测值：
对于非负整数 x，初始猜测值设为 x 本身，因为平方根不会超过 x 本身。
牛顿迭代公式：
牛顿迭代法的公式为：new_guess=(old_guess+x/old_guess)/2
这个公式通过不断迭代来逼近平方根的值。
精度控制：
使用 epsilon 来控制精度，初始设为 1。
每次迭代后，将 epsilon 除以 10，逐步减小精度要求，确保最终结果的准确性。
取整：
使用 Math.floor 函数来确保结果只保留整数部分。

5.有效的完全平方数(与上类似）

/*** @param {number} num* @return {boolean}*/
var isPerfectSquare = function(num) {if(num===1)return truelet left=1;let right=Math.floor(num/2)+1;//天天天，你条件写错了！！！！while(left<=right){let mid = Math.floor((left+right)/2);let square=mid*mid;if(square===num){return true;}else if(square>num){right=mid-1;}else{left=mid+1;}}return false;
};

题目：给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。
- 解析：这是二分查找算法的最基本应用。通过设定左右指针，不断缩小搜索范围，直到找到目标值或确定目标值不存在。
题目：给定一个按照非递减顺序排列的整数数组nums，和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target，返回[-1, -1]。
- 解析：这个问题可以先用二分查找找到目标值的一个位置，然后通过双指针从中间向两边扩散，找到目标值的开始位置和结束位置。这种方法的时间复杂度为O(log n + k)，其中n是数组的长度，k是目标值在数组中出现的次数。
题目：在旋转排序数组中查找目标值（假设数组中不存在重复元素）。
- 解析：旋转排序数组是指一个递增排序数组经过一次旋转得到的数组。这个问题可以通过修改二分查找算法来解决。首先，找到数组中的“旋转点”（即数组从递增变为递减的点），然后根据目标值与旋转点的大小关系，在数组的左侧或右侧进行二分查找。
题目：在有序数组中查找第一个大于给定值的元素。
- 解析：这个问题可以通过二分查找算法来解决。在每次迭代中，根据中间元素与目标值的大小关系，更新搜索范围，直到找到第一个大于目标值的元素或确定不存在这样的元素。