- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
二分查找(Binary Search)是一种在有序数组中查找特定元素的高效算法。它的基本思想是将目标值与数组中间的元素进行比较,如果目标值小于中间元素,则在数组的左半部分继续查找,否则在右半部分查找,不断缩小搜索范围,直到找到目标值或确定目标值不存在为止.
二分查找也叫折半查找,比如在一个有序的数组里面找到目标值,它是一种查询效率比较高的算法,时间复杂度O(logn)。比如在下面数组找到 6.首先在定位到两侧,也就是最大值和最小值。并找到中间和目标值比较.
中间值是 23,比目标值更大,就要缩小范围,中间值作为最大值,在中间值左边的区域再找到中间值和目标值比较.
以此类推,一直缩小范围,直到找到目标值,或者搜索完数据.
public static int binarySearch(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) {
return mid; // 找到目标值,返回索引
} else if (nums[mid] < target) {
left = mid + 1; // 目标值在右半部分
} else {
right = mid - 1; // 目标值在左半部分
}
}
return -1; // 目标值不存在
}
left 和 right 记录最小值和最大值的下标,left + (right - left) / 2 是查询中间下标,有的查询下标直接使用(left + right)/2,这样可能会超出时间范围。通过 left = mid + 1 或者 right = mid - 1 不断缩小范围.
有序的数组在某个下标上进行旋转:
将旋转点之后的数据整体放在数组之前:
上面说二分查询只是针对有序的数组,这又不是一个有序的数组,但是数组分成两部分有序的数组.
public int search(int[] nums, int target) {
int length = nums.length;
if (length == 0) {
return -1;
}
if (length == 1) {
return nums[0] == target ? 0 : -1;
}
int left = 0,right = length-1;
while (left <= right) {
int mid = left + (right - left)/2;
if (nums[mid] == target) {
return mid;
}
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
right = mid -1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[length - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
求解平法根,也就是k² <= x,也就是求解 k 最大整数值。对 x 进行二分查找.
public int mySqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
int left = 1;
int right = x;
int result = -1;
while (left <= right) {
int mid = left + (right - left)/2;
if ((long)mid * mid > x) {
right = mid - 1;
} else {
result = mid;
left = mid + 1;
}
}
return result;
}
旋转数组是要么全部有序,要么两个部分有序。每次做二分查找,每次mid和最右边值作比较,会出现两种情况.
第一种情况是 nums[pivot] < nums[high],如上图所示,此时最小值应该在 piot 的左侧,height 缩进到 pivot 的位置.
第二种情况是 nums[piot] > num[height], 如上图所示,此时最小值应该在 piot 的右侧,low 缩进到 piot 的位置.
class Solution {
public int findMin(int[] nums) {
int low = 0,height = nums.length-1;
while (low < height) {
int mid = low + (height - low)/2;
if (nums[mid] < nums[height]) {
height = mid;
} else {
low = mid + 1;
}
}
return nums[low];
}
}
public boolean isPerfectSquare(int num) {
if (num <= 2) {
return true;
}
int left = 2,right = num/2,y;
long square;
while (left <= right) {
y = left + (right - left)/2;
square =(long) y * y;
if (square == num) {
return true;
}else if (square > num) {
right = y - 1;
}else {
left = y + 1;
}
}
return false;
}
搜索有序的数组的元素,使用二分查找是一个高效率的查询方法。定位左右两侧最大值和最小值,找到中间值。然后通过目标值和中间值做对比,缩小搜索范围,直到搜索找到符合条件数据.
有时候无需全部有序,两部分有序也是可以通过二分查找找到符合要求的数据.
最后此篇关于图解LeetCode算法汇总——二分查找的文章就讲到这里了,如果你想了解更多关于图解LeetCode算法汇总——二分查找的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
1迷茫的小黑 小黑最近有点郁闷。 手头的工作不是特别喜欢,技术退步有点严重,于是想出去看看机会。 小黑通过朋友内推,前几天去一家名叫宇节蹦跶的公司面试,被一些问题三连击直接跪掉了。图片
前言 很多朋友都会遇到这样的问题,明明在cmd中装好了lxml库,可pycharm就是运行不了,用pycharm自己的装库方法却装不上库…… 真让人恼火……………… 今天就来教大家怎
1、MySQL安装 MySQL的下载 http://dev.mysql.com/downloads/mysql/ MySQL版本选择 MySQL功能自定义选择安装 功能自定义选择
很多次遇到在pycharm中无法安装第三方库的情况,今天我就遇到了,找了很多办法都没用 但是在pycharm中配置anaconda环境之后再从anaconda下载安装你所需要的库就可以diy完决你
今天小编给大家记录下docker在centos7下不能下载镜像timeout的问题,先给大家说下问题的来龙去脉。 问题描述: 昨天买了六个月阿里云服务器的学生机用来部署毕设环境,在鼓捣docke
解决问题: 因为FileZilla这个程序是直接解压缩之后便可以使用的,每次都需要到文件所在目录Filezilla/bin/filezilla下双击执行,太麻烦,若直接使用软链接的话也可以实现,s
浏览器与IIS服务器与.Net FrameWork关系 Asp.Net ASP.Net是一种动态网页技术,在服务器端运行.Net代码,动态生成HTML,然后响应给浏览器。
织梦程序是国内比较多人使用的一套cms系统,用dedecms织梦程序如何做中英文网站,今天就给大家来一个详细的图文教程,希望能帮助到大家。 以下所讲的和截图是本人用dedecms织梦程序制作过的一
又是dns,小编最近写了好多关于dns的话题。当然小编今天写的与以往也略有不同,今天小编来告诉大家我们中国各地首选的dns地址各是什么。首选dns地址,顾名思义是是我们电脑上网时首选的地址。如果我
1、认识kafka 面试官提问:什么是 Kafka ?用来干嘛的? 官方定义如下: Kafka is used for building real-time data pipelines
VSCode卸载后进行重新安装,发现新安装的还有原来的一些配置,卸载的不彻底,有时候也容易出问题,可按照如下方法卸载干净: 1.进入控制面板卸载VSCode,也可以在VSCode的安装目录下用程序
1、软件版本 首先我先安装了 python 2.7 pip是 8.1.2 2、当我要安装pil时,我在cmd下面输入:pip install pil 错误提示是: co
intellij idea是一款非常优秀的软件开发工具,它拥有这强大的插件体系,可以帮助开发者完成很多重量级的功能。今天,我们来学习一下如何安装和卸载intellij idea的插件。 intel
本文旨在分类讲述执行计划中每一种操作的相关信息。 数据访问操作 首先最基本的操作就是访问数据。这既可以通过直接访问表,也可以通过访问索引来进行。表内数据的组织方式分为堆(Heap)和B树,其中表
看完这篇专题,你能在30分钟内在你的电脑上开始玩Wordpress,并向互联网上其他用户提供服务(如果可能:))。 目录: 一;配置服务器; 二;调试服务器; 三;安装Wordpress;
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界. 这篇CFSDN的博客文章详解在Ubuntu 中修改默认程序(图解)由作者收集整理,如果你对这篇文
两两交换链表中的节点 力扣题目链接(opens new window) 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实
1. 首先参考idea热部署同行经验分享: intellij idea 4种配置热部署的方法 2. idea 热部署实战: springboot项目: 不要引入热部署工具包spring-boo
下载之后安装目录下 Servers的文件夹是服务端安装包,Tools文件夹是客户端安装包,SQL2005安装就必须先安装Tools(客户端),之后再安装Servers,如果不按顺序安装SQL2005
我重装系统后就安装了SQL Server2008R2,第一次使用时在修改表结构的时候经碰到这样一个警告【不允许保存更改。您所做的更改要求
我是一名优秀的程序员,十分优秀!