LeetCode刷题系列之数组--0704.二分查找(JAVA版本)

#0704.二分查找

难度：简单

题目：给定一个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

解法一：基础解法

public static int search(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {if (nums[i] == target) {return i;}}return -1;}

二分查找解法【重点】

二分查找的原理就是设置left与right两个索引，并通过两个索引的中间值middle 分别从最左侧与最右侧向中间查找目标值，通过一步步缩小范围最终找到目标值。

二分查找也可分为两种解法，区别在于左右区间的设置不同。

二分查找解法1：[left,right]

public static int search(int[] nums, int target) {int left = 0 ;int right = nums.length -1 ; //区间右闭合，right索引从最右侧数开始while(left <= right) { // right索引有意义，所以符号为 <=int middle = (left + right) / 2 ;if (nums[middle] > target) {right = middle - 1 ;} else if(nums[middle] < target) {left = middle + 1 ;} else {return middle;}}return -1;}

注意：

while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

二分查找解法2：[left,right)

public static int search(int[] nums, int target) {int left = 0 ;int right = nums.length; // 右开区间，right索引从数组外开始while(left < right) { // right无意义，所以符号为 <int middle = (left + right) / 2 ;if (nums[middle] > target) {right = middle; // 时刻记得right为开区间索引值，是不能被取到的} else if(nums[middle] < target) {left = middle + 1 ;} else {return middle;}}return -1;}

注意：

while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

总结：

二分法的两种解法是在数学意义上的不同，要充分理解区间定义不同所带来的代码方面的差异。

最后附上LeetCode本题的链接，完全理解了的小伙伴可以去尝试一下这道题：

https://leetcode-/problems/binary-search/

如果觉得《LeetCode刷题系列之数组--0704.二分查找(JAVA版本)》对你有帮助，请点赞、收藏，并留下你的观点哦！