本文已收录于专栏 《Java入门一百例》 【《Java入门100练》|【第26天】给定 n 个元素的升序数组nums,求实现一个函数在nums中寻找target的下标 | 初识二分查找】
学习指引
- 序、专栏前言
- 序、本章前言
- 二分查找
- 一、【例题1】
-
- 1、题目描述
- 2、解题思路
- 3、模板代码
- 4、代码解析
- 三、推荐专栏
- 四、课后习题
序、专栏前言 ?? 本专栏开启,目的在于帮助大家更好的掌握学习
Java
,特别是一些Java学习者
难以在网上找到系统地算法学习资料帮助自身入门算法,同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。?? 但最最主要的还是需要独立思考,对于本专栏的所有内容,能够进行完全掌握,自己完完全全将代码写过一遍,对于算法入门肯定是没有问题的。
?? 算法的学习肯定不能缺少总结,这里我推荐大家可以到高校算法社区将学过的知识进行打卡,以此来进行巩固以及复习。
??学好算法的唯一途径那一定是题海战略,大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。
序、本章前言 ??今天的内容十分之重要,第一次涉及到二分查找,这是一个经典中的经典,基础中的基础,却又是能折磨死一大片人的算法。无论在任何地方,它都是一个很重要的考点,今天我们只是初略涉及。
二分查找 ??二分查找是一个优化算法,它通常能将 O ( n ) O(n) O(n)的查找复杂度优化到 O ( l o g n ) O(logn) O(logn)。使用二分查找的前提是具有——二段性。很多人总是存在误区,使用二分查找必须得有单调性,这观点是错误的,单调性只是属于二段性的一种,是我们常遇见能使用二分的场景,而实际上满足二段性我们就可以二分。
??那么什么是二段性呢?
??对于某一范围内的数据,存在一个临界点,使得临界点某一侧的所有数据都满足某一性质,另外一侧都不满足这一性质。??二分有一个核心的
check
函数,这个函数的逻辑便是寻找这个临界条件的性质,使得一边均满足,一边均不满足。当我们的mid
落在满足性质的区间上,我们会保留该点,当落在不满足的区间上,我们会舍去该点,最后左右指针将会无限逼近这个临界点退出循环,我们得到答案。一、【例题1】 1、题目描述
??给定一个2、解题思路n
( 1 ≤ n ≤ 10000 ) (1 \leq n \leq 10000) (1≤n≤10000)个元素有序的(升序)整型数组nums
和一个目标值target
,写一个函数搜索nums
中的target
,如果目标值存在返回下标,否则返回-1
。保证数组内不存在重复元素
- ( 1 ) (1) (1)像二分查找的主要核心,就是寻找二段性,对于存在单调性的数组很好寻找二段性。由于数组升序,我们可知对于
target
左边的元素一定都是小于target
,对于target
右边的元素,一定都是大于等于target
(这个右边包括target
的位置),由此找到二段性。 - ( 2 ) (2) (2)结合上述分析,当
mid
落在不符合的区间,我们使l=mid+1
,因为不符合的区间在左边,当落在符合的区间时,我们使r=mid
,因为符合的区间在右边,如果数组中存在target
,那么等循环结束后应当满足nums[l]==nums[r]==target
,否则说明无解。
class Solution {
public int search(int[] nums, int target) {
int n=nums.length;
int l=0;
int r=n-1;
while(l>1;
if(nums[mid]>=target) r=mid;
else l=mid+1;
}
return nums[r]==target?r:-1;
}
}
4、代码解析
- ( 1 ) (1) (1)为什么循环条件写成
l
,而不是 l<=r
呢?因为l
的结束条件是 l==r
,此时l
和r
在用一位置,我们最后无需去担心答案是落在l
上还是r
上,所以推荐大家都这么写。 - ( 2 ) (2) (2)
l+r>>1
是什么意思?>>
是右移操作符,本质上也就是将l+r
的和除以2
,和(l+r)/2
无区别,只不过>>
更快那么一点。如果l+r
的和有可能爆int
,应该写成r-l+l/2
- ( 3 ) (3) (3)最后为什么还要判断
nums[r]==target
?虽然数组满足二段性,而并不意味着target
一定在数组中,比如有数组 [ 1 , 2 , 4 , 5 ] [1,2,4,5] [1,2,4,5],target
为3的情况下,数组同样具有二段性,但原数组中临界点却并不一定存在答案。
序号 | 题目链接 | 难度评级 |
---|---|---|
1 | 二分查找 | 2 |
1 | 搜索插入位置 | 2 |
推荐阅读
- leetcode刷题|LeetCode 第63场双周赛复盘
- Leetcode|leetcode:第260场周赛复盘
- 《Java入门100练》|【第25天】给定一个长度为 n 的数组,统计每个数出现的次数 | 计数哈希
- 《Java入门100练》|【第24天】给定一个长度为 n 的数组,将元素 X 插入数组指定的位置 | 数组插入操作
- Leetcode复盘|LeetCode 第 298 场周赛
- 《力扣周赛题解》|【周赛复盘】LeetCode第298场单周赛
- 《力扣周赛题解》|【周赛复盘】LeetCode第80场双周赛
- 索引|《穿越 Java | 第三章 - 基础语法篇》
- 大厂面试题精华总结|SpringCloud面试百题集