公司网站建设服务机构,龙华做棋牌网站建设,淘宝怎么下载视频,新品发布会宣传文案文章目录 前言一、通常情况下的两种二分查找的形式1.经典款2.左闭右开款 二、做题题解中的二分查找的变形1.有效的完全平方数#xff08;LeetCode367#xff09; 前言
因为最近刷到二分查找的题目学习到了不同的写法#xff0c;因此在这里总结一下#xff0c;方便之后遗忘… 文章目录 前言一、通常情况下的两种二分查找的形式1.经典款2.左闭右开款 二、做题题解中的二分查找的变形1.有效的完全平方数LeetCode367 前言
因为最近刷到二分查找的题目学习到了不同的写法因此在这里总结一下方便之后遗忘再来复习。 一、通常情况下的两种二分查找的形式
1.经典款
这一款学过二分查找的基本都会写不难理解。
public int search(int[] nums, int target) {int left 0;int right nums.length - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {right mid - 1;} else if (nums[mid] target) {left mid 1;} else {return mid;}}return -1;
}2.左闭右开款
public int search(int[] nums, int target) {int left 0;int right nums.length;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {right mid;} else if (nums[mid] target) {left mid 1;} else {return mid;}}return -1;
}这里为什么称之为左闭右开款这是我的理解因为经典款的[left,right]就是表示寻找的目标元素就在这个区间里如果mid指向的元素不为目标元素那么就会直接地跳过mid让mid1或者mid-1来构建一个新的闭区间[left,right]。第二个不一样它开局就将right赋为数组长度我们都知道数组下标最多是长度减一因此left和right就构成了左闭右开的区间因此在这个区间里面去找目标元素不能够出现rightleft的情况并且当mid指向的元素大于目标元素时虽然这时的mid时不合条件的但是也直接作为了区间的右端点这就是因为右端点是开的原因不合条件的mid根本不包含在寻找目标元素的区间中。
二、做题题解中的二分查找的变形
1.有效的完全平方数LeetCode367
题目描述 给你一个正整数 num 。如果 num 是一个完全平方数则返回 true 否则返回 false 。 完全平方数 是一个可以写成某个整数的平方的整数。换句话说它可以写成某个整数和自身的乘积。 不能使用任何内置的库函数如 sqrt 。 题解代码如下
class Solution {public boolean isPerfectSquare(int num) {long l 0, r num;while (l r) {long mid l r 1 1;if (mid * mid num) l mid;else r mid - 1;}return r * r num;}
}
这里我刚看非常疑惑为什么mid哪里要多加一等等。后来我结合第二种二分查找把这种写法给看懂了。首先它是使用了左开右闭的区间所以当mid * mid num时直接让lmid。其次为什么在mid那里加一其实是为了防止死循环如果只剩下两个元素分别为leftright指向如果不加一每次算出的mid赋给leftleft和right计算之后的mid还是等于left原值如果加一算出来的mid就会指向right的位置最终避免循环。还有一点就是为什么要将和的情况放在一起如mid * mid num我猜可能是因为方便因为最终right肯定是left靠拢的将这两种情况放一起并不影响结果。然后后面我来给出如果是左闭右开的区间按照这里题解的思想代码怎么写。
class Solution {public boolean isPerfectSquare(int num) {long l 1;long r num1;while (l r) {long mid (l r ) / 2;if (mid * mid num) {l mid1;} else {r mid;}}return (l * l) num;}
}
