您的位置:首页 > 健康 > 养生 > 特种作业人员成绩查询_专业建筑设计网站平台_自动连点器_个人免费建站系统

特种作业人员成绩查询_专业建筑设计网站平台_自动连点器_个人免费建站系统

2025/3/18 9:07:13 来源:https://blog.csdn.net/qq_56101688/article/details/146327927  浏览:    关键词:特种作业人员成绩查询_专业建筑设计网站平台_自动连点器_个人免费建站系统
特种作业人员成绩查询_专业建筑设计网站平台_自动连点器_个人免费建站系统

二分查找伪代码

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 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
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com