leetcode34题
常规解法：for循环遍历有序序列，使用两个变量标记第一个数的位置和最后一个数位置。时间复杂度为O(n)。
进阶解法：使用二分搜索法搜索左右边界，时间复杂度O(logn)。
搜索左边界的方法：
1. 首先与正常二分搜索法一样，找到序列中与目标值相同的值；
2. 正常的二分搜索找到正常的值时退出循环即可，而搜索左边界不退出循环，令搜索区间的right等于该目标值的索引减1，收缩右侧边界。换句话来说是依次搜索目标值左侧区间中是否有与目标值相等的数；
3. 搜索右边界同理。
```Java
public static int leftBound(int[] nums, int target) {
//当有序序列为空时
if(nums.length==0){
return -1;
}
int left = 0;//定义左边界
int right = nums.length - 1;//定义右边界
while (left <= right) {
int mid = left + (right - left) / 2;
//搜索区间[left,mid-1]
if (nums[mid] > target) {
right = mid - 1;
}
//搜索区间[right,mid+1]
else if (nums[mid] < target) {
left=mid+1;
}
//搜索区间[left,mid-1]
else if (nums[mid] == target) {
right=mid-1;
}
}
//检查目标值大于序列最大值和目标值小于序列最小值
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
public static int rightBound(int[] nums, int target) {
//当有序序列为空时
if(nums.length==0){
return -1;
}
int left = 0;//定义左边界
int right = nums.length - 1;//定义右边界
while (left <= right) {
int mid = left + (right - left) / 2;
//搜索区间[left,mid-1]
if (nums[mid] > target) {
right = mid - 1;
}
//搜索区间[right,mid+1]
else if (nums[mid] < target) {
left=mid+1;
}
//搜索区间[left,mid+1]
else if (nums[mid] == target) {
left=mid+1;
}
}
//这里改写right越界条件，因为移动的是right
if (right < 0 || nums[right] != target)
return -1;
return right;
}
```
有了搜索左右边界我们就可以查找某个元素的第一个和最后一个元素。时间时间复杂度O(logn)。到这里我就把二分搜索的三种类型都介绍给大家了。
注意：二分搜索其实有很多中写法，有左开右闭区间，左闭右开区间，但我还是建议大家按我一样只写左闭右闭统一成一种形式，这样代码很好记，while循环的判断条件left《right，以后闭着眼睛都可以写出来。
2.二分查找leetcode704题
要求：给定n个元素的升序整型数组和一个目标值，返回目标值下标，不存在返回-1。
解题思路：这道题其实在上面已经做过了，二分搜索的进阶我们都可以闭住眼睛写出来，这道题当然不在话下，在找到目标值的时候返回即可。
```Java
public static int binarySearch(int[] nums, int target) {
//当有序序列为空时
if(nums.length==0){
return -1;
}
int left = 0;//定义左边界
int right = nums.length - 1;//定义右边界
while (left <= right) {
int mid = left + (right - left) / 2;
//搜索区间[left,mid-1]
if (nums[mid] > target) {
right = mid - 1;
}
//搜索区间[right,mid+1]
else if (nums[mid] < target) {
left=mid+1;
}
//搜索区间[left,mid+1]
else if (nums[mid] == target) {
return mid;
}
}
//不在搜索区间内直接返回-1即可，不需要判断左右指针越界
return -1;
}
```
3.搜索插入位置
leetcode35题
要求：给定⼀个排序数组和⼀个⽬标值，在数组中找到⽬标值，并返回其索引。如果⽬标值不存在于数组中，返回它将会被按顺序插⼊的位置。
解题思路：这道题就是考察搜索左侧边界的二分算法的细节理解。当目标元素不存在数组中时，搜索左侧边界的二分搜索的返回值可以做以下几种解读：
1. 返回值是nums中大于等于target的最小元素索引；
2. 返回的值是target应该插入在nums中的索引位置；
3. 返回的这个值是 nums 中⼩于 target 的元素个数。
⽐如在有序数组 nums = [2,3,5,7] 中搜索 target = 4，搜索左边界的⼆分算法会返回 2，也就是5的索引，你带⼊上⾯的说法，都是对的。
所以以上三种解读都是等价的，可以根据具体题⽬场景灵活运⽤，显然这⾥我们需要的是第⼆种。 返回的值是nums中小于target的元素个数。
目标元素不存在数组中，右边界的解读也是一样的，有兴趣的同学可以自己试一试。
```Java
public static int leftBound(int[] nums, int target) {
//当有序序列为空时
if(nums.length==0){
return -1;
}
int left = 0;//定义左边界
int right = nums.length - 1;//定义右边界
while (left <= right) {
int mid = left + (right - left) / 2;
//搜索区间[left,mid-1]
if (nums[mid] > target) {
right = mid - 1;
}
//搜索区间[right,mid+1]
else if (nums[mid] < target) {
left=mid+1;
}
//搜索区间[left,mid-1]
else if (nums[mid] == target) {
right=mid-1;
}
}
//检查目标值大于序列最大值和目标值小于序列最小值
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
```
4.总结
从上面的三道题中，二分搜索的三种基本类型都给出了，按照我的模板学习，闭着眼睛都可以写出来。有了二分的基础之后需要培养发现二分的能力，在以后的刷题中我们会经常遇到那种很难分解出二分的题。
