目录
前言
1、二分查找
2、在排序数组中查找元素的第一个和最一个位置
3、搜索插入位置
4、 x 的平⽅根
5、山峰数组的峰顶
6、寻找峰值
前言
本文主要介绍二分算法的思想和相关题目。很多介绍都说二分算法往往需要有序，但实际有序并不是使用二分算法的核心，使用二分算法的核心应该是两段性，也就是能根据题目条件把整个区间分为两段。
1、二分查找
链接：https://leetcode.cn/problems/binary-search/
本题是最基础的二分查找算法，之后的题目都是建立在本题的基础上：
a. 定义 left ， right 指针，分别指向数组的左右区间。
b. 找到待查找区间的中间点 mid ，找到之后分三种情况讨论：
- i. arr[mid] == target 说明正好找到，返回 mid 的值；
- ii. arr[mid] > target 说明 [mid, right] 这段区间都是⼤于 target 的，因此舍去右边区间，在左边 [left, mid -1] 的区间继续查找，即让 right = mid -1 ，然后重复 2 过程；
- iii. arr[mid] < target 说明 [left, mid] 这段区间的值都是⼩于 target 的，因此舍去左边区间，在右边 [mid + 1, right] 区间继续查找，即让 left = mid +1 ，然后重复 2 过程；
c. 当 left 与 right 错开时，说明整个区间都没有这个数，返回 -1 。
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;//防止溢出if(nums[mid]==target){return mid;}else if(nums[mid]<target){left=mid+1;}else{right=mid-1;}}return -1;}
}2、在排序数组中查找元素的第一个和最一个位置
链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
二分查找总共有三种方式，分别是最基本的查找方法，查找右边一段的左边界和查找左边一段的右边界。基本二分查找用的很少，比如本题如果使用基本查找方法找到之后再左右遍历在特殊情况下时间复杂度会退化到O(n)。左右边界查找方法代码如下：
class Solution {public int[] searchRange(int[] nums, int target) {int[] ret=new int[2];ret[0]=-1;ret[1]=-1;if(nums.length==0){return ret;}//找左端点int left=0,right=nums.length-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]>=target){right=mid;}else{left=mid+1;}}if(nums[left]==target){ret[0]=left;}else {return ret;}//找右端点left=0;right=nums.length-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]<=target){left=mid;}else{right=mid-1;}}if(nums[right]==target){ret[1]=right;}else {return ret;}return ret;}
}3、搜索插入位置
链接：https://leetcode.cn/problems/search-insert-position/description/
本题可以将区间分为两部分，左区间小于等于目标值，右区间大于目标值，然后根据寻找右端点的写法就可以解题。（实际分为左区间小于右区间大于等于找左端点会更好一些，一般要返回的值在哪个区间内就把等号加到那个区间里）。
class Solution {public int searchInsert(int[] nums, int target) {int left=0,right=nums.length-1;if(nums[left]>target){return left;}while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]<=target){left=mid;}else{right=mid-1;}}if(nums[left]==target){return left;}else{return left+1;}}
}4、 x 的平⽅根
链接：https://leetcode.cn/problems/sqrtx/description/
本题和上一题类似，可以将区间分为两部分，左区间小于等于目标值，右区间大于目标值，然后根据寻找右端点的写法就可以解题。
class Solution {public int mySqrt(int x) {long left=0,right=x;while(left<right){long mid=left+(right-left+1)/2;if(mid*mid<=x){left=mid;}else{right=mid-1;}}return (int)left;}
}5、山峰数组的峰顶
链接：https://leetcode.cn/problems/peak-index-in-a-mountain-array/submissions/592155701/
本题可以根据题目要求把数组分为两段，第一段满足每个元素大于前一个元素，第二段满足每个元素小于前一个元素，使用二分查找。
class Solution {public int peakIndexInMountainArray(int[] arr) {int left=0,right=arr.length-1;while(left<right){int mid=left+(right-left+1)/2;if(arr[mid]>arr[mid-1]){left=mid;}else{right=mid-1;}}return left;}
}6、寻找峰值
链接：https://leetcode.cn/problems/find-peak-element/
如果满足当前值大于前一个值，那么当前点的右边一定存在峰值，如果满足当前值小于前一个值，那么 当前点的左边一定存在峰值，只要能将区间分割成两部分并利用条件逐渐排除其中的一部分，那么就可以使用二分查找。
class Solution {public int findPeakElement(int[] nums) {int left=0,right=nums.length-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]>nums[mid-1]){left=mid;}else{right=mid-1;}}return right;}
}
