二分查找常用于在有序数组中查找符合条件的元素。
实际上，即使数组不是有序的，但具有“二段性”则也能使用二分查找算法来求解。
对于二分查找算法，有三个模版，分别在以下的一、二题中体现：
1.朴素的二分查找模板：
while(left<=right){
int mid=left+(right-left)/2;
int x=nums[mid];
if(target<x){
right=mid-1;
}else if(target>x){
left=mid+1;
}else{
return mid;
}
}2.查找左边界的二分模板：
while(left<right){//不能等于，否则可能会死循环
//定义中点
int mid=left+(right-left)/2;
int x=nums[mid];
//求左边界，就以target的左边界将数组划分为＞=target和＜target两个部分
if(x>=target){
right=mid;
}else{
left=mid+1;
}
}3.查找右边界的二分查找：
while(left<right){//不能等于，否则可能会死循环
//定义中点
int mid=left+(right-left+1)/2;
int x=nums[mid];
//求右边界，就以target的右边界将数组划分为＜=target和＞target两个部分
if(x＜=target){
left=mid;
}else{
right=mid-1;
}
}一、二分查找
题目链接：https://leetcode.cn/problems/binary-search/
题目：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。
你必须编写一个具有 O (log n) 时间复杂度的算法。
示例 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中，用left和right来指向数组的左右两边，mid=left+(right-left)/2为中间值。
因为数组是有序数组，每次我们把mid对应的元素于target进行比较，如果mid元素大于target，则舍去右边区间使right=mid-1；
如果mid元素小于target则舍去左边区间使left=mid+1；
这样每次查找都能将数组的范围缩小一半，直到mid元素等于target，就返回mid。
代码及结果：
class Solution {
public int search(int[] nums, int target) {
int left=0,right=nums.length-1;
while(left<=right){
int mid=left+(right-left)/2;
int x=nums[mid];
if(target<x){
right=mid-1;
}else if(target>x){
left=mid+1;
}else{
return mid;
}
}
return -1;
}
}
二、在排序数组中查找元素的第一个和最后一个位置
题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
题目：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O (log n) 的算法解决此问题。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]示例 3:
输入: nums = [], target = 0
输出: [-1,-1]
思路：
大体上将这道题分为两个步骤解决：
1.求出其符合条件的左边界
对于求解左边界：在这个数组中，也是具有“二段性”的，可以将其划分为两部分。
⭐️求左边界就从左边界划分，将数组划分为：＜target和＞=target的两部分
nums[mid]<target：left=mid+1；
nums[mid]>=target：right=mid；注意：这里right不能为mid-1，因为此时mid对应元素可能就是target的左边界，如果-1就越界了；
❓因为满足条件时，right被赋值为mid，于是就引出了两个细节问题：
- 循环条件不能是left＜=right了，因为当left==right进入判断后，此时left==right==mid，会在right=mid处发生死循环。
- 求中点的操作不是mid=left+(right-left+1)/2（靠右的中点），而是mid=left+(right-left)/2（靠左的中点）。如果只有两个数left和right时，mid是靠右的 等于right，依然会在right=mid处死循环。
2.求出其符合条件的右边界。
同上。
代码及结果：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[]ret=new int[2];
ret[0]=ret[1]=-1;
if(nums.length==0){
return ret;
}
if(nums==null){
return ret;
}
//初始步骤
int left=0,right= nums.length-1;
//求左端点
while(left<right){//不能等于，否则可能会死循环
//定义中点
int mid=left+(right-left)/2;
int x=nums[mid];
//判断,以mid为界重新划分
if(x>=target){
right=mid;
}else{
left=mid+1;
}
}
//放入数组ret
if(nums[left]==target){
ret[0]=left;
}
//求右端点
left=0;
right= nums.length-1;
while(left<right){
int mid=left+(right-left+1)/2;
int x=nums[mid];
if(x<=target){
left=mid;
}else{
right=mid-1;
}
}
//放入数组ret
if(nums[left]==target){
ret[1]=left;
}
return ret;
}
}
三、搜索插入位置
题目链接：https://leetcode.cn/problems/search-insert-position/
题目：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O (log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
思路：
这道题显然不能使用朴素的二分算法求解。
题目给出的target可能在nums中找不到，于是可以将nums划分为＜target和＞=target两部分。
代码及结果：
class Solution {
public int searchInsert(int[] nums, int target) {
//初始
int left=0,right=nums.length-1;
//开始循环
while(left<right){
//设置中点
int mid=left+(right-left)/2;
int x=nums[mid];
//判断
if(x>=target){
right=mid;
}else{
left=mid+1;
}
}
if(nums[left]<target) return left+1;
return left;
}
}
四、X的平方根
题目链接：https://leetcode.cn/problems/sqrtx/
题目：
给你一个非负整数 x，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow (x, 0.5) 或者 x ** 0.5。
示例 1：
输入：x = 4
输出：2示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842...，由于返回类型是整数，小数部分将被舍去。
思路：
假设有一个从1到x的升序数组nums，我们只需要拿mid遍历到的数的平方与x做比较，实现二分查找即可。
这里举一个例子：假设输入的x=8，那么正确的答案应该是2.
如果划分的区间是>=2和<2，那在第一个区间里，2～2.8的部分是不符合条件的。
因此划分的区间应该是<=2和>2。
代码及结果：
class Solution {
public int mySqrt(int x) {
if(x<1) return 0;
//初始化
long left=1,right=x;
//循环
while(left<right){
//设置中点
long mid=left+(right-left+1)/2;
long n=(long)mid*mid;
if(n<=x){
left=mid;
}else{
right=mid-1;
}
}
return (int)left;
}
}
五、山脉数组的峰顶索引
题目链接：https://leetcode.cn/problems/peak-index-in-a-mountain-array/
题目：
给定一个长度为 n 的整数山脉数组 arr，其中的值递增到一个峰值元素然后递减。
返回峰值元素的下标。
你必须设计并实现时间复杂度为 O (log (n)) 的解决方案。
示例 1:
输入: arr = [0,1,0]
输出: 1示例 2:
输入: arr = [0,2,1,0]
输出: 1示例 3:
输入: arr = [0,10,5,2]
输出: 1
思路：
可以根据二段性将数组划分为两个部分：
- arr[mid-1]<arr[mid]-->left=mid
- arr[mid-1]>arr[mid]-->right=mid-1
代码及结果：
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left=1,right=arr.length-2;
//循环
while(left<right){
//设置中点
int mid=left+(right-left+1)/2;
//判断
if(arr[mid-1]<arr[mid]){
left=mid;
}else{
right=mid-1;
}
}
return left;
}
}
六、寻找峰值
题目链接：https://leetcode.cn/problems/find-peak-element/
题目：
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums [-1] = nums [n] = -∞。
你必须实现时间复杂度为 O (log n) 的算法来解决此问题。
示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。示例 2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5，其峰值元素为 6。
思路：
题目中给出的数组可能会有多个符合条件的峰值，但是只需给出一种即可。
这个数组依然具有二段性：
对于一个arr[mid]：
- 如果有arr[mid]>arr[mid+1]，则说明这里是降序的，那么它的左边必定有一个峰值，那就往左边寻找，right=mid；
- 如果有arr[mid]<arr[mid+1]，则说明这里是升序的，那么它的右边必定有一个峰值，那就往右边寻找，left=mid+1；
代码及结果：
class Solution {
public int findPeakElement(int[] nums) {
if(nums.length==0||nums.length==1) return 0;
//初始(要考虑边界)
int left=0,right=nums.length-1;
//循环
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]<nums[mid+1]){
left=mid+1;
}else{
right=mid;
}
}
return left;
}
}
七、寻找旋转排序数组中的最小值
题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
题目：
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
- 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a [0], a [1], a [2], ..., a [n-1]] 旋转一次的结果为数组 [a [n-1], a [0], a [1], a [2], ..., a [n-2]]。
给你一个元素值互不相同的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。
你必须设计一个时间复杂度为 O (log n) 的算法解决此问题。
示例 1:
输入: nums = [3,4,5,1,2]
输出: 1
解释：原数组为 [1,2,3,4,5]，旋转 3 次得到输入数组。示例 2:
输入: nums = [4,5,6,7,0,1,2]
输出: 0
解释：原数组为 [0,1,2,4,5,6,7]，旋转 4 次得到输入数组。示例 3:
输入: nums = [11,13,15,17]
输出: 11
解释：原数组为 [11,13,15,17]，旋转 4 次得到输入数组。
思路：
这道题类似于寻找峰值，画图如下：
根据二段性：
- arr[mid]>arr[n-1]：left=mid+1；
- arr[mid]<arr[n-1]：right=mid；
代码及结果：
class Solution {
public int findMin(int[] nums) {
//初始化
int left=0,right= nums.length-1;
//循环
while(left<right){
//设置中点
int mid=left+(right-left)/2;
//判断
if(nums[mid]>nums[nums.length-1]){
left=mid+1;
}else{
right=mid;
}
}
return nums[left];
}
}
八、点名
题目链接：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
题目：
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
示例 1：
输入：records = [0,1,2,3,5]
输出：4示例 2：
输入：records = [0, 1, 2, 3, 4, 5, 6, 8]
输出：7
思路：
这道题具有二段性：
- arr[mid]=mid：left=mid+1；
- arr[mid]!=mid：right=mid；
代码及结果：
class Solution {
public int takeAttendance(int[] records) {
int left=0,right=records.length-1;
while(left<right){
int mid=left+(right-left)/2;
if(mid==records[mid]){
left=mid+1;
}else{
right=mid;
}
}
return records[left]==left?left+1:left;
}
}