寻找指定位置
二分法
二分法的难点在于其细节而不是其思想，所以学习过程中要明白其思想，知道所有细节，并能够用代码实现出来。
二分法主要有两种写法
left<=right
public int search(int[] nums, int target) {
int l=0;
int r=nums.length-1;
//因为left == right是有意义的，所以使用 <=
while (l<=r){
// 防止溢出
int mid = l+(r-l)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
// 当前数字一定比targer小，所以下一次查询的范围是 【mid+1，r】
l=mid+1;
}else if(nums[mid]>target){
//当前数字一定比targer大，所以下一次查询的范围是 【l，mid-1】
r=mid-1;
}
}
return -1;
}
left<right
public int searchTwo(int[] nums, int target) {
int l=0;
// 定义target在左闭右开的区间里，即：[left, right)
int r=nums.length;
// 使用< 是因为left == right在区间[left, right)是没有意义的
while (l<r){
// 防止溢出
int mid = l+(r-l)/2;
if(nums[mid]==target){
return mid;
//当 nums[mid] 被检测之后，下一步的搜索区间应该去掉 mid 分割成两个区间
//即 [left, mid) 或 [mid + 1, right)
}else if(nums[mid]<target){
//由于判断的区间范围是 【left，right）,此时 mid 位置的数是小于target的
//下一步判断时就可以跳过 mid ，从mid +1 开始
//判断范围为 [middle + 1, right)
l=mid+1;
}else if(nums[mid]>target){
//由于判断的区间范围是 【left，right）,此时 mid 位置的数是大于target的
//判断范围为【left, middle)
// 若 r=mid-1 ，则本来 mid 与 l 产生的判断范围被忽略掉了
r=mid;
}
}
return -1;
}
关于left<right 中nums[mid]>target 时 r=mid
举个例子
-1 0 3 5 9 12
----------------------
0 1 2 3 4 5
target=3
l=0，r=6
第一次 mid = （0+6）/2 =3
num[3] =5>3
若 r =mid-1
则 r=3-1=2
第二次 mid = （0+2）/2=1
num[1]=0 <3
l=mid+1 =1+1=2 = r l==r while 循环退出，找不到target了
但本例子中是有targer=3的
------------------------
选用r =mid
则 r=3
第二次 mid = （0+3）/2=1
num[1]=0 <3
l=mid+1 = 1+1 =2 < r
第三次 mid = （2+3）/2=2
num[2]=3 找到了target
在排序数组中查找元素的第一个和最后一个位置
对于一个数，第一个位置就是找到其在数组中的左侧位置，最后一个位置就是数组中的右侧位置
采用 left<=right 进行二分查找，所以判断区间为[left,right]
寻找左侧边界的二分搜索
5 7 8 8 8 8 9
-------------------------
0 1 2 3 4 5 6
----左边界求解，关于nums[mid]==target的处理
0+6）/2=3
arr【3】=8=8
r=mid=3
0+3)/2=1
arr[1]=7<8
left=mid+1=2
2+3)/2=2
arr[2]=8=8
r=mid=2
2+2)/2=2
arr[2]=8=8
r=mid=2;
....开始死循环了，所以r在处理时不能等于mid
------重新开始
0+6）/2=3
arr【3】=8=8
《-----
r=mid-1=3-1=2 每次将左边界减小
0+2)/2=1
arr[1]=7<8
left=mid+1=2 左边界右移
2+2)/2=2
arr[2]=8=8
r=mid-1=2-1=1；
left>right 跳出循环
返回left
---------左边界求解，关于nums[mid]>target的处理
5 8 8 9 9 9 9
-------------------------
0 1 2 3 4 5 6
0+6）/2=3
arr[3]=9>8
r=mid-1=3-1=2
0+2)/2=1
arr[1]=8=8
r=mid-1=1
0+1)/2=0
arr[0]=5<8
left=mid+1=0+1=1
1+1)/2=1
arr[1]=8=8
r=mid-1=0
left>right 跳出循环
返回left
寻找右侧边界的二分搜索
5 7 8 8 8 8 9
-------------------------
0 1 2 3 4 5 6
----右边界求解，关于nums[mid]==target的处理
0+6）/2=3
arr【3】=8=8
l=mid+1=3+1=4
4+6)/2=5
arr[5]=8=8
left=mid+1=4+1=5
5+6)/2=5
arr[5]=8=8
left=mid+1=5+1=6
6+6)/2=6
arr[6]=9>8
r=mid-1=6-1=5
left>right 跳出循环
返回right
---------右边界求解，关于nums[mid]>target的处理
8 8 9 9 9 9 9
-------------------------
0 1 2 3 4 5 6
0+6）/2=3
arr[3]=9>8
r=mid-1=3-1=2
0+3）/2=1
arr[1]=8=8
left=mid+1=1+1=2
2+3)/2=2
arr[2]=9>8
r=mid-1=2-1=1
left>right 跳出循环
返回right
以上分析之后写的代码：
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length==0 || (nums.length==1&&nums[0]!=target)){
return new int[]{-1,-1};
}
int left = searchLeft(nums,target);
int right = searchRight(nums,target);
return new int[]{left,right};
}
private int searchRight(int[] nums, int target) {
int l=0;
int r=nums.length-1;
while (l<=r){
int mid = l+(r-l)/2;
if(nums[mid]==target){
l=mid+1;
}else if(nums[mid]>target){
r=mid-1;
}else if(nums[mid]<target){
l=mid+1;
}
}
return r;
}
private int searchLeft(int[] nums, int target) {
int l=0;
int r=nums.length-1;
while (l<=r){
int mid = l+(r-l)/2;
if(nums[mid]==target){
r=mid-1;
}else if(nums[mid]>target){
r=mid-1;
}else if(nums[mid]<target){
l=mid+1;
}
}
return l;
}
}
坑1:没有考虑到返回的左右边界会越界
2 2
---
0 1
target=1
(此用例为右边界越界)
0+1)/2=0
arr[0]=2>1
r=mid-1=0-1=-1
left>right 跳出循环
但此时 ritht=-1 数组越界了
所以返回时要判断 right<0
2 2
---
0 1
target=3
(此用例为左边界越界)
0+1)/2=0
arr[0]=2>1
r=mid-1=0-1=-1
left>right 跳出循环
但此时 ritht=-1 数组越界了
所以返回时要判断 right<0
修改返回值：
r>=0 ? r : -1;
l<=nums.length-1 ? l : -1;
坑2:万一target不在数组中
返回时进行判断 l 与 r 位置的元素是不是target
r>=0 ? (nums[r]==target ? r:-1) : -1;
l<=nums.length-1 ? ( nums[l]==target ? l:-1) : -1;
完成ac代码
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length==0 || (nums.length==1&&nums[0]!=target)){
return new int[]{-1,-1};
}
int left = searchLeft(nums,target);
int right = searchRight(nums,target);
return new int[]{left,right};
}
private int searchRight(int[] nums, int target) {
int l=0;
int r=nums.length-1;
while (l<=r){
int mid = l+(r-l)/2;
if(nums[mid]==target){
l=mid+1;
}else if(nums[mid]>target){
r=mid-1;
}else if(nums[mid]<target){
l=mid+1;
}
}
return r>=0 ? (nums[r]==target ? r:-1) : -1;
}
private int searchLeft(int[] nums, int target) {
int l=0;
int r=nums.length-1;
while (l<=r){
int mid = l+(r-l)/2;
if(nums[mid]==target){
r=mid-1;
}else if(nums[mid]>target){
r=mid-1;
}else if(nums[mid]<target){
l=mid+1;
}
}
return l<=nums.length-1 ? ( nums[l]==target ? l:-1) : -1;
}
}