当前位置: 首页 > article >正文

数组题型-二分查找-JS

二分查找伪代码

1.定义 target 是在⼀个在左闭右闭的区间⾥,也就是[left, right]

    let left=0;
    let right=nums.length-1;// 定义target在左闭右闭的区间⾥,[left, right]
    
    while(left<=right){// 当left==right,区间[left, right]依然有效,所以⽤ <=
    let middle=Math.floor((left+right)/ 2); // 防⽌溢出
        if(nums[middle]===target) return middle;// 数组中找到⽬标值,直接返回下标
        if (nums[middle]>target){
            right=middle-1;// target 在左区间,所以[left, middle - 1]
        }
        if(nums[middle]<target){
            left=middle+1;// target 在右区间,所以[middle + 1, right]
        }
    }
    // 未找到⽬标值
    return -1;
时间复杂度: O(log n)
空间复杂度: O(1)

2.target 是在⼀个在左闭右开的区间⾥,也就是[left, right) 

其实就是right取值的时候取不到。

    let left=0;
    let right=nums.length-1;// 定义target在左闭右开的区间⾥,[left, right)
    
    while(left<right){// 当left==right,区间[left, right)无效效,所以⽤ <
    let middle=Math.floor((left+right)/ 2); // 防⽌溢出
        if(nums[middle]===target) return middle;// 数组中找到⽬标值,直接返回下标
        if (nums[middle]>target){
            right=middle;// target 在左区间,所以[left, middle)
        }
        if(nums[middle]<target){
            left=middle+1;// target 在右区间,所以[middle + 1, right)
        }
    }
    // 未找到⽬标值
    return -1;

leetcode相关题目

704.二分查找
35. 搜索插⼊位置
34. 在排序数组中查找元素的第⼀个和最后⼀个位置
69.x 的平⽅根
367. 有效的完全平⽅数
小技巧:在循环结束时,left 和 right 的值已经交叉,left 指向第一个大于目标值的位置,right 指向最后一个小于目标值的位置。
704.二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1


示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

 就是二分法基础 背熟 没什么好说的

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {

    let left=0;
    let right=nums.length-1;
    
    while(left<=right){
    let middle=Math.floor((left+right)/ 2);
        if(nums[middle]===target) return middle;
        if (nums[middle]>target){
            right=middle-1;
        }
        if(nums[middle]<target){
            left=middle+1;
        }
    }
    return -1;
};
35.搜索插入位置

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 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

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 为 无重复元素 的 升序 排列数组
  • -104 <= target <= 104

 直接一部分是二分法查值,另一部分就是我们说的技巧在循环结束时,left 和 right 的值已经交叉,left 指向第一个大于目标值的位置,right 指向最后一个小于目标值的位置。

我们要把元素放在合适的位置,我们找到的值不存在于数组中,也就是说最终的left和right是距离目标最接近的位置。但left指向的是第一个大于目标值的位置,因此把元素放入left现在的位置就可以。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left=0;
    let right=nums.length-1;
    while(left<=right){
        let middle=Math.floor((left+right)/2)
        if(nums[middle]===target) return middle;
        if(target>nums[middle]) left=middle+1;
        if(target<nums[middle]) right=middle-1;
    }
    return left;
};

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

给你一个按照非递减顺序排列的整数数组 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]

提示:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

我们可以通过二分查找找到一个元素的位置,以此为起点,向两边查找相等的元素即可。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let middle = Math.floor((left + right) / 2);
        if (nums[middle] === target) {
            // 找到目标值,查找起始和结束位置
            let start = middle;
            let end = middle;
            // 向左查找起始位置
            while (start > 0 && nums[start - 1] === target) {
                start--;
            }
            // 向右查找结束位置
            while (end < nums.length - 1 && nums[end + 1] === target) {
                end++;
            }
            return [start, end];

        } else if (nums[middle] < target) {
            left = middle + 1; // 目标值在右半部分
        } else {
            right = middle - 1; // 目标值在左半部分
        }
    }
    return [-1,-1]

};

69.x 的平⽅根

给你一个非负整数 x ,计算并返回 x 的 算术平方根

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5

示例 1:

输入:x = 4
输出:2

示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

提示:

  • 0 <= x <= 231 - 1

也是二分查找,注意我们的技巧,在循环结束时,left 和 right 的值已经交叉,left 指向第一个大于目标值的位置,right 指向最后一个小于目标值的位置。因此这里应该是right right是最接近目标值又小于目标值的。

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let left=0;
    let right=x;
    while(left<=right){
        let middle=Math.floor((left+right)/2)
        if(middle*middle===x) return middle
        if(middle*middle>x) right=middle-1;
        if(middle*middle<x) left=middle+1;
    }
    return right
};

367.有效的完全平⽅数

给你一个正整数 num 。如果 num 是一个完全平方数,则返回 true ,否则返回 false

完全平方数 是一个可以写成某个整数的平方的整数。换句话说,它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数,如  sqrt

示例 1:

输入:num = 16
输出:true
解释:返回 true ,因为 4 * 4 = 16 且 4 是一个整数。

示例 2:

输入:num = 14
输出:false
解释:返回 false ,因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示:

  • 1 <= num <= 231 - 1

这个和上题类似 但是更加简单 只要对数进行二分判断 如果输的平方可以和它相等 那就是找到了;否则当left和right相交时,就是不存在。

/**
 * @param {number} x
 * @return {boolean}
 */
var isPerfectSquare = function(x) {
    let left=0;
    let right=x;
    while(left<=right){
        let middle=Math.floor((left+right)/2)
        if(middle*middle===x) return true
        if(middle*middle>x) right=middle-1;
        if(middle*middle<x) left=middle+1;
    }
    return false
};


http://www.kler.cn/a/589386.html

相关文章:

  • 实战:自适应均衡的设计与实现
  • 【Docker】容器中安装cron命令
  • 使用 Docker 部署 MySQL 8
  • TensorFlow 基本原理与使用场景
  • 移除元素(快慢指针)
  • Linux第六讲----git与gdb
  • 文本检测-文本内容审核-文本过滤接口如何用PHP调用?
  • 市长海报/ Mayor‘s posters
  • L2-3 花非花,雾非雾
  • maven使用install将jar包编译到本地仓库管理
  • 【系统架构设计师】操作系统 - 文件管理 ② ( 位示图 | 空闲区域 管理 | 位号 | 字号 )
  • 牛客周赛 Round 85
  • ElementUI 表格中插入图片缩略图,鼠标悬停显示大图
  • 电脑型号与尺寸
  • Leetcode Hot 100 200.岛屿数量
  • 【Agent】OpenManus-Flow-BaseFlow详细分析
  • element-ui progress 组件源码分享
  • 蓝牙技术联盟中国实体成立!华为、小米发声支持本土化战略
  • 实战ansible-playbook
  • 《C#上位机开发从门外到门内》3-3:基于USB的设备管理系统