- 前言
- 题目
- 题解
- 参考资料
哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。
这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。
题目
题目来源leetcode
leetcode地址：704. 二分查找，难度：简单。
题目描述(摘自leetcode)：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间
本地调试代码：
class Solution {
public int search(int[] nums, int target) {
....
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = new int[]{-1,0,3,5,9,12};//这里修改数组内容
System.out.println(solution.search(arr, 2));//数组、目标值
}
}
题解
思路：
看清题干"整型数组 nums为有序升序"，我们直接可以直接通过二分法来进行定位指定元素。 中间数组索引：第一次为整个数组的中间元素下标，之后根据比对的元素大小来进行左半区间、右半区间定位 其他见注释即可。
代码：时间复杂度：O(logn)、空间复杂度：O(1)
class Solution {
public int search(int[] nums, int target) {
//边界条件：数组大小为空、为null情况直接返回-1
if (nums.length == 0 || nums == null) {
return -1;
}
int begin = 0;//左索引
int end = nums.length - 1;//右索引
while (begin <= end) { //终止条件，一旦不符合条件就说明所有的情况都已经比对结束，没有在数组中找到指定元素
int mid = begin + (end - begin) / 2; //中间索引
if (nums[mid] == target) { //情况一：一旦中间值=目标值，说明找到，直接返回下标
return mid;
} else if (nums[mid] < target) { //情况二：一旦中间值<目标值，那就说明可能的目标值在右半区间，左索引=mid，之后就会最大程度进行中间索引的定位
begin = mid + 1;
} else {//情况三：同情况二差不多，中间值>目标值，此时目标值就在左半区间
end = mid - 1;
}
}
return -1;
}
}
根据最优题解优化以及细节部分：包含=>的意思是左边为原本洗的代码，右边为参考最优解
第10行： int mid = (begin+end)/2 => int mid = begin+(end-begin)/2 。
思考：若是begin与end的值都是一个大致，原本begin+end就可能出现值溢出情况，最后的结果可能与原值不符，导致最终结果有误。目的就是防止溢出情况。
第14、16行：若是begin=mid以及end=mid的话，就会出现死循环的情况，如案例[-1, 0, 3, 5, 9, 12]中找目标值2。所以左右边界赋值时要+-1。
最后看一下leetcode执行结果：
参考资料
[1]. leetcode题解
[2]. 代码随想录leetcode刷题—二分查找题解
我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！
欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料
Q群：851968786 我们可以一起探讨学习
注明：转载可，需要附带上文章链接
