0717-7821348
政策法规

政策法规

您现在的位置: 首页 > 政策法规
[算法有必要死 第3期] 旋转数组的二分查找
2019-06-20 21:31:04

Talk is cheap. Show me the code.

2019

根本二分查找算法

二分查找是针对次序存储的有序序列的;二分查找的根本思维是:将方针元素与序列中位数比较,假如大于中位数则在右半段序列查找,反之在左半段查找。


为了能够便利表明(以升序序列为例),设置两个索引值start,end表明查找规模即下图中的两个灰色箭头,设置一个符号mid表明当时规模的中心方位,存在且仅存在如下三种状况:

1. 假如values[mid]==target,则return mid

2. 假如values[mid]<target,则start=mid+1

3. 假如values[mid]>target,则end=mid-1


例如一组元素values[2,3,5,12,23,24,25,26,27],查找方针target=26的进程如下图所示:


二分查找之所以快速是因为:相关于序列长度而言,它只需求查看很少几个条目就能找到方针元素或者是确认方针元素不存在。


二分查找的思维仍是很简略的,详细完成如下:

public static int binarySearch(int[] values,int target){
    if(values==null){
        throw new NullPointerException("values==null");
    }
    boolean asc=values[0]<values[values.length-1]?true:false;
    int start=0;
    int end=values.length-1;
    while(start <= end){
        int mid=start+(end-start)/2;
        if(target==values[mid]) {
            return mid;
        }else if(target<values[mid]){
            if(asc){
                end=mid-1;
            }else{
                start=mid+1;
            }
        }else{
            if(asc){
                start=mid+1;
            }else{
                end=mid-1;
            }
        }
    }
    return -1;
}



旋转数组的二分法

下面评论一下旋转数组的二分查找算法;

旋转有序数组也是一个有序序列,只不过它是错位的,比方下面的两个序列都是旋转有序数组,旋转数组中存在一个旋转点,升序下的旋转点便是最小元素,而降序下旋转点是最大元素。

关于旋转数组的二分查找,能够分以下两种状况评论,一是已知旋转点的方位,二是不知道旋转点方位。


已知旋转点

01

假如现已直到旋转点的方位rotatedPoint,问题瞬间变得简略,算法思路和根本二分查找算法共同;

 

仅有改动的是需求一个映射公式:j=(rotatedPoint+i)%values.length(其间i表明下标(即算法中的mid等),j表明实践引证元素的下标。该公式在升序降序下都建立。)

 

依据这个公式,只需求对根本的算法略加改善即可(实践上只需求改动mid,因为二分查找只会在mid处进行比较):

 

留意:因为不是严厉排序的,不能再运用

values[0]<values[values.length-1]?true:false;

条件判别是否是升序,能够改为values[rotatedPoint]<values[values.length-1]?true:false;

public static int rotatedBinarySearch(int[] values,int target,int rotatedPoint){
    if(values==null){
        throw new NullPointerException("values==null");
    }
    boolean asc=values[rotatedPoint]<values[values.length-1]?true:false;
    int start=0;
    int end=values.length-1;
    while (start<=end){
        int mid=start+(end-start)/2;
        int map=binarySearchIndexMap(mid,values.length,rotatedPoint);
        if(values[map]==target) {
            return map;
        }else if(values[map]<target){
            if(asc){
                start=mid+1;
            }else {
                end=mid-1;
            }

        }else{
            if(asc){
                end=mid-1;
            }else {
                start=mid+1;
            }
        }
    }
    return -1;

private static int binarySearchIndexMap(int index,int length,int rotatedPoint){
    return (rotatedPoint+index)%length;
}


不知道旋转点

02

不知道旋转点的状况比较复杂,以升序序列为例;

 

相同需求判别方针在左半边仍是右半边,只不过无法直接判别,这与中位数和旋转点的方位相关,所以首先要判别旋转点和中位数的方位联系


假如旋转点在中位数的右侧,应该由values[start]<=values[mid]判别出来,中位数在左边便是!( values[start]<=values[mid]);

旋转点在中位数右侧时,假如方针在左半边的话,因为左半边是彻底升序的;所以判别条件应该是:

values[start]<=target<values[mid]

在左半边便是!( values[start]<=target<values[mid]);

 

旋转点在中位数左边时,假如方针在右半边的话,因为右半边是升序的,所以判别条件应该是:values[mid]<target<=values[end],在左半边取反即可。

 

关于降序而言,进行相同的剖析,能够得到完好的判别条件:


依据以上条件,修正二分查找算法代码完成:

static int rotatedBinarySearch(int[] values,int target,boolean asc){
    if(values==null){
  [算法有必要死 第3期] 旋转数组的二分查找;      throw new NullPointerException("values==null");
    }
    int start=0;
    int end=values.length-1;
    while(start<=end){
        int mid=start+(end-start)/2;
        if(values[mid]==target){
            return mid;
        }else {
            if(asc){  //升序摆放
     &nbs[算法有必要死 第3期] 旋转数组的二分查找p;          if(values[mid]>=values[start]){
                    if(values[mid]>target&&values[start]<=target){
                        end=mid-1;
                    }else {
                        start=mid+1;
                    }
                }else {
                    if(values[mid]<target&&values[end]>=target){
                        start=mid+1;
                    }else {
                        end=mid-1;
                    }
                }
            }else {
   &nbs[算法有必要死 第3期] 旋转数组的二分查找p;            if(values[mid]>=values[end]){
                    if(values[mid]>target&&values[end]<=target){
                        start=mid+1;
                    }else{
               &nbs[算法有必要死 第3期] 旋转数组的二分查找p;        end=mid-1;
                    }
                }else{
                    if(values[mid]<target&&values[start]>=target){
                        end=mid-1;
                    }else{
                        start=mid+1;
          绝世武魂夕厉          }
                }
            }
        }
    }
    return -1;
}



 二分法的溢出危险

在代码中mid=start+(end-start)/2,而没有写为mid=(start+end)/2是因为(start+end)/2或许存在溢出的要挟:假如数组很长,start和end能够会非常大,start+end会变得更大,或许超过了int的最大规模。所以改写为mid=start+(end-start)/2;




END

SmartPig

长按二维码重视我