1、查找数组中特定值出现的位置
public static int binarySearch(int[] nums,int target){
//寻找数组中target的元素下标,数组升序排列
int l=0,r=nums.length-1;
while(l<r){//当l=r时区间内只有一个元素,结束循环判断其是否满足即可
int m=(l+r)/2;
//要避免l或r一直保持不变的情况,比如l=m,m=(l+r),l会一直保持不变
if(nums[m]==target){
return m;
}
else if(nums[m]<target){
l=m+1;
}
else{
r=m-1;
}
}
if(nums[l]!=target){
return -1;//如果找不到
}
return l;
}
Q:循环终止的条件为什么是while(l<r)而不是while(l<=r)?
A:当l=r时区间内只有一个元素,可以结束循环,然后判断区间内的这一个元素是否等于target即可,如果等于就返回其下标,不满足返回-1.网上也有人用while(l<=r)来作为循环结束条件,也是可以的,但代码中的其他部分需要根据这个循环结束条件来进行调整。我更习惯用while(l<r)来作为循环结束条件。
Q:什么时候m=(l+r)/2?什么时候m=(l+r+1)/2?
A:前者是m向下取整,后者是向上取整。考虑只剩两个元素时,保证l或r不要一直不变,导致死循环即可。如果l=m,m=(l+r),那么l会一直保持不变。举个例子,如果l=2,r=3,假设调整边界的时候l=m,若m=(l+r)/2,定边界的时候如果落到l=m,则l=m=2,相当于l的值一直是2,m的值也会一直是2,死循环。要避免这种情况,可以调整边界 ,让m=(l+r+1)/2。
2、查找数组中特定值第一次出现的位置
查找数组中值为target元素第一次出现的位置。
public static int binarySearchLeft(int[] nums,int target){
//寻找数组中等于target的元素最小下标,数组升序排列
int l=0,r=nums.length-1;
while(l<r){
int m=(l+r)/2;
if(nums[m]==target){//要使下标尽可能小,抛弃右半边元素
r=m;
}
else if(nums[m]<target){
l=m+1;
}
else{
r=m;
}
}
if(nums[l]!=target){
return -1;
}
return l;
}
3、查找数组中特定值最后一次出现的位置
查找数组中值为target元素最后一次出现的位置。
public static int binarySearchRight(int[] nums,int target){
//寻找数组中等于target的元素最大下标,数组升序排列
int l=0,r=nums.length-1;
while(l<r){
int m=(l+r+1)/2;
if(nums[m]==target){
l=m;
}
else if(nums[m]<target){
l=m;
}
else{
r=m-1;
}
}
if(nums[l]!=target){
return -1;
}
return l;
}
4、查找数组中小于等于特定值的元素的最大下标
寻找数组中小于等于target的元素的最大下标。
public static int binarySearchUpper(int[] nums,int target){
//寻找数组中小于等于target的元素最大下标,数组升序排列
int l=0,r=nums.length-1;
while(l<r){
int m=(l+r+1)/2;
if(nums[m]<=target){
l=m;
}
else{
r=m-1;
}
}
if(nums[l]>target){
return -1;
}
return l;
}
5、查找数组中大于等于特定值的元素的最小下标
寻找数组中大于等于target的元素的最小下标。
public static int binarySearchLower(int[] nums,int target){
//寻找数组中大于等于target的元素最小下标,数组升序排列
int l=0,r=nums.length-1;
while(l<r){
int m=(l+r)/2;
if(nums[m]>=target){
r=m;
}
else{
l=m+1;
}
}
if(nums[l]<target){
return -1;
}
return l;
}
Comments NOTHING