二分查找算法---Java实现

目录

一、二分查找算法的基本思想

二、二分查找算法的基本实现

（1）第一种基本实现

（2）第二种基本实现

三、二分查找算法的平衡版

四、Java中的二分查找API

五、二分查找处理重复值

（1）LeftMost

（2）RightMost

（3）LeftMost改进版

（4）RightMost改进版

---

一、二分查找算法的基本思想

加入在一个数组中查找某个目标值tar，大概历程如下（要注意二分查找算法的实现是基于数组已经排序过的，这里是升序，也就是从小到大）：

开始有两个前后指针low,high分别指向初始位置和末尾位置（因为是数组，所以两个指针的值等于0和数组长度-1，注意数组是从索引0开始的）。

中间位置mid=(low+high)/2

（1）如果目标值tar的值大于中间值,说明查找的位置是在右边，即是在中间值到后指针high之间，所以，开始在那个区间段查找，即low=mid+1

（2）如果目标值tar的值小于中间值，说明查找的位置是在左边，即是在前指针到中间值之间，所以，开始在那个区间段查找，即high=mid-1

（3）如果目标值等于中间值，说明已经查找到，返回索引位置即可。

二、二分查找算法的基本实现

对于这两种方式的区别也没有什么大的区别，主要就是思路不一样，也没有其他什么地方不同（个人观点）

（1）第一种基本实现

public class Main {
    public static void main(String[] args) {
        int[] a={1,3,5,7,9};
        System.out.println(BinarySeatch(a,9));
    }
    //二分查找算法模板
    //参数分别表示查找数组和查找目标，返回值是查找到的位置，没有查找到返回-1
    public static int BinarySeatch(int[] a,int target){
        //数组是之前就已经排序过，从小到大
        int i=0,j=a.length-1;
        while(i<=j){
            //这里求中间值，简单点就是(i+j)/2
            int m=(i+j)>>>1;
            if(target>a[m]){
                i=m+1;
            }
            else if(target<a[m]){
                j=m-1;
            }
            else{
                return m;
            }
        }
        return -1;
    }
}

（2）第二种基本实现

//第二种二分查找算法的基本实现
    public static int BinarySearch2(int[] a,int target){
        int i=0,j=a.length;
        while(i<j){
            int mid=(i+j)>>>1;
            if(target>a[mid]){
                i=mid+1;
            }
            else if(target<a[mid]){
                j=mid;
            }
            else{
                return mid;
            }
        }
        //没查找到
        return -1;
    }

三、二分查找算法的平衡版

出现平衡板的原因是会因为上面的基本算法的查找有可能左边查找次数过多，有可能右边查找次数过多，具体的大家可以好好理解一下。

//二分查找算法平衡版
    public int BinarySearchPeng(int[] a,int target){
        //前后指针的意思是i一开始可能会被选中，为目标值，j不会！所以区间可以理解成左闭右开
        int i=0,j=a.length;
        //循环条件是这个表示,两个指针内没有其他元素，当然i指向的也可能就是，后面跳出循环会查看究竟是不是。
        while(j-i>1){
            int mid=(j+i)>>>1;
            //如果目标值小于中间值，在左边，j=mid，这个是因为一开始j的值不是数组索引，不在数组内，所以这次可能就是，要j=mid
            
            if(target<a[mid]){
                j=mid;
            }
            //如果目标值大于中间值或者等于中间值，i=mid
            else{
                i=mid;
            }
        }
        //比较是否相等放到了循环外面
        if(target==a[i]){
            return i;
        }
        else{
            return -1;
        }
    }

四、Java中的二分查找API

Java中其实也是有二分查找实现的API，在Arrays包下。具体用法如下：

 public static void main(String[] args) {
        int[] a={1,3,5,7,9,11,13,15};
       //二分查找API
        //第一个参数是数组，第二个参数是查找的目标值
        //查找到的返回值是索引位置，未查找到的返回值=-(应该插入的位置+1)
        System.out.println(Arrays.binarySearch(a,10));

        //插入值的索引
        //API的返回值=-（low+1)
        System.out.println("插入值得索引="+Math.abs(Arrays.binarySearch(a,10)+1));
    }

五、二分查找处理重复值

（1）LeftMost

假如数组中有重复值，如：1,4,6,6,6,6,8

这时候我们想要查找的目标值是6，并且希望获得的是最左边的，该算法如下：

 public int LeftMostBasic(int[] a,int target){
        int i=0,j=a.length-1;
        int candidate=-1;//记录位置，重复的位置
        while(i<=j){
            int mid=(i+j)>>>1;
            if(target>a[mid]){
                i=mid+1;
            }
            else if(target<a[mid]){
                j=mid-1;
            }
            else{
                //相等
                candidate=mid;
                //因为是查找最左边，所以还要往左边找
                j=mid-1;
            }

        }
        return candidate;
    }

（2）RightMost

与LeftMost对应的，他查找的是最右边的。

如：1,4,6,6,6,6,8

查找6的话，返回的是索引值5.

    public int RightMostBasic(int[] a,int target){
        int i=0,j=a.length-1;
        int candidate=-1;
        while(i<=j){
            int mid=(i+j)>>>1;
            if(target>a[mid]){
                i=mid+1;
            }
            else if(target<a[mid]){
                j=mid-1;
            }
            else{
                candidate=mid;
                //选取最右边，所以继续在右边找
                i=mid+1;
            }
        }
        return candidate;
    }

（3）LeftMost改进版

为什么改进版呢？其实也就是我们想让返回值更加有用一点，大致思路没有变化。具体如下：

返回值就是>=target的最左索引

 //LeftMost改进版
    public int LeftMostUpgrade(int[] a,int target){
        int i=0,j=a.length-1;
        while(i<=j){
            int mid=(i+j)>>>1;
            if(target<a[mid]){
                j=mid-1;
            }
            else{
                i=mid+1;
            }
        }
        //返回值i的含义是：
        //（1）如果找到目标值，表示的是最左边目标的索引位置
        //（2）如果没有找到目标，表示的是比目标大的并且最靠左边的索引
        return i;
    }

（4）RightMost改进版

返回值<=target的最右索引

 //RightMost改进版
    public int RightMostUpgrade(int[] a,int target){
        int i=0,j=a.length-1;
        while(i<=j){
            int mid=(i+j)>>>1;
            if(target>=a[mid]){
                i=mid+1;
            }
            else{
                j=mid-1;
            }
        }
        //返回值的含义：
        //(1)目标值存在的话，返回的是最右边目标值索引
        //(2)目标不存在的话，返回的是小于目标值的最右边的索引
        return i-1;
    }

（5）应用

LeftMost:>=target的最左边索引

RightMost:<=target的最右边索引

假如数组是上图[1,2,4,4,7,7,7]

（1）应用1

求排名

如2的排名是2,5插进去排名则是6。

即2的排名=LeftMost(2)+1

5的排名=LeftMost(5)+1

（2）应用2

求前任

如2的前任是1，索引就是0

4的前任是2，索引就是1

5的前任是4（最右边的4），索引是4

即4的前任=LeftMost(4)-1

5的前任-LeftMost(5)-1

（3）应用3

求后任

如5的后任=RightMost(5)+1

（4）范围查询

如查找小于4的（x<4）? ? ? ? ?则是[0,LeftMost(4)-1](这里说的索引)

如查找小于等于4的(x<=4)? ? 则是[0,RightMost(4)]

如查找大于4(x>4)? ? ? ? ? ? ? ? ?则是[RightMost(4)+1,+无穷大)

如查找大于等于4(x>=4)? ? ? ? 则是[LeftMost(4),+无穷大)

如查找(x>=4&&x<=7)? ? ? ? ? ?则是[LeftMost(4),RightMost(7)]

如查找(x>4&&x<7)? ? ? ? ? ? ? ?则是[RightMost(4),LeftMost(7)-1]