二分查找伪代码
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] <= 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 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
};