LeetCode：704. 二分查找

简介

题目链接：https://leetcode.cn/problems/binary-search/description/

解决方式：数组 + 二分查找

这是作者学习众多大神的思路进行解题的步骤，很推荐大家解题的时候去看看题解里面大佬们的思路、想法！

二分查找系列题：
34. 在排序数组中查找元素的第一个和最后一个位置（进阶）

二分查找

思路：题目所给数组是升序的，所以我们可以初始化两个左右指针，分别指向第一个和最后一个元素。每次迭代的时候先计算中间点，根据中间点判断向何处收缩区间。

具体可参考labuladong大佬关于二分查找一系列的详细题解！

classSolution{publicintsearch(int[]nums,inttarget){// 左右边界intleft=0;intright=nums.length-1;// 二分查找while(left<=right){// 中点// 由数学公式 (left + right) / 2 等价而来，防止整数溢出intmid=left+(right-left)/2;if(nums[mid]>target){// 目标在左侧，向左收缩right=mid-1;}elseif(nums[mid]<target){// 目标在右侧，向右收缩left=mid+1;}else{// 中点元素就是目标元素，直接返回// 由于此题找到即可，而不是寻找左右边界，所以直接返回returnmid;}}// 没有找到，返回 -1return-1;}}

拓展

寻找左边界

思路：为了寻找左边界，中间点等于目标元素时不能直接返回，而是进一步向左收缩，减小范围，直到找到左边界。

intleft_bound(int[]nums,inttarget){intleft=0,right=nums.length-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}elseif(nums[mid]>target){right=mid-1;}elseif(nums[mid]==target){// 别返回，进一步减小范围right=mid-1;}}// 检查 left 越界的情况// 一种是目标元素比数组所有元素都大，left = nums.length// 一种是目标元素在数组范围中，但是没有目标元素if(left>=nums.length||nums[left]!=target)return-1;returnleft;}

寻找右边界

思路：与寻找右边界同理。

intright_bound(int[]nums,inttarget){intleft=0,right=nums.length-1;while(left<=right){intmid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}elseif(nums[mid]>target){right=mid-1;}elseif(nums[mid]==target){// 别返回，进一步减少范围left=mid+1;}}// 检查 right 越界的情况// 一种是目标元素比数组所有元素都小，right < 0// 一种是目标元素在数组范围中，但是没有目标元素if(right<0||nums[right]!=target)return-1;returnright;}