数组题型-二分查找-JS

    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;

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

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

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