卷进大厂系列之LeetCode刷题笔记：二分查找（简单）

LeetCode刷题笔记：二分查找（简单）

学算法，刷力扣，加油卷，进大厂！

题目描述

力扣题目链接
给定一个 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

提示：

• 你可以假设 nums 中的所有元素是不重复的。
• n 将在 [1, 10000]之间。
• nums 的每个元素都将在 [-9999, 9999]之间

涉及算法

这道题目属于简单题型，涉及到数据结构中的数组。对于数组我们要知道以下内容：

• 数组是存储在连续内存空间的相同类型数据的集合
• 数组下标都是从0开始
• 数组在内存空间的地址都是连续的

那么根据题目，我们可以提炼的关键点：

• 该数组为有序数组
• 数组元素无重复

根据这些关键点很容易想到二分法，因为这些都是二分法的前提条件（小本本记一下）。既然用二分法，那就要注意下二分法的边界条件（这个是比较容易写错的），这就要求我们保证区间的不变，开闭区间（例如＜还是＜= ， 要保持不变）。

上面都搞清楚了，就可以开始写了，不懂的可以留言讨论！

题目解答

Java题解一

classSolution{publicintsearch(int[] nums,int target){int left =0;//定义左边界int right = nums.length-1;//定义有边界//循环（二分法开始）while(left <= right){//这里使用的左右都是闭区间，所有left = right时候也是可以的int medium = left +((right-left)/2);//防止溢出if(target < nums[medium]){//target小于中间值，在左区间循环
                right = medium -1;}elseif(target > nums[medium]){//target大于中间值，在右区间循环
                left = medium +1;}else{return medium;//target刚好等于中间值}}return-1;//没找到target}}

复杂度分析

时间复杂度：O(log2n)，其中 n 是数组的长度。

空间复杂度：O(1)。