二分查找伪代码
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;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相关题目
给定一个
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提示：
- 你可以假设
nums中的所有元素是不重复的。n将在[1, 10000]之间。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;
};给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
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] <= 104nums为 无重复元素 的 升序 排列数组-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] <= 109nums是一个非递减数组-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 middleif(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 trueif(middle*middle>x) right=middle-1;if(middle*middle<x) left=middle+1;}return false
};