Java二分查找-图文

我会带着你远行 2024-04-20 12:26 2阅读 0赞

### 一、二分查找概念 ###

二分查找也叫[折半查找][Link 1]，是在一组**有序**(升序/降序)的数据中查找一个元素，它是一种效率较高的查找方。

### 二、二分查找原理 ###

> 1.二分查找的数组必须是有序数值型数组。
> 
> 2.将想要查找的目标元素与查找范围内的中间元素进行比较，如果相等，查找结束，反之，把目标元素分到较大或者是较小的范围在进行比较。
> 
> 3.通过分组可将查找范围缩小一半。
> 
> 4.重复步骤二，直到目标元素与查找范围内中间元素相等或者没有这个目标元素，查找结束。
> 
> 5.二分查找的时间复杂度O(log2n)

### 三、二分查找的具体步骤 ###

前提：给定一个内含n个元素的有序数组A，满足A0<=A1<=A2<=·······<=An-1,一个待查值target，

如果找到返回索引

如果找不到返回索引-1

> 1、设置i=0,j=n-1
> 
> 2、如果i>j,结束查找，没有找到，返回-1
> 
> 3、设置m为中间索引，则m=floor((i+j)/2), floor是向下取整（<=（i+j）/2 的最小整数)
> 
> 4、如果 target<Am ,设置j=m-1, 跳到第2步
> 
> 5、如果 Am< target,设置i=m+1, 跳到第2步
> 
> 6、如果 Am= target,结束查找，找到了！

### 四、图示所示-基础版 ###

**查找target=4**

![dbc8b4185b3e4d2690bdd0844bc103bc.png][]

![7901d1abd25d43c6a26a886b4ce9ecdb.png][]

![c06edbfda4814cc388ff567ef684b00d.png][]

![50bd93e069a6403a8cfb5742b1d5d795.png][]

![847ec344fd0c4e1991f7b501d302961e.png][]

![a88af61a07aa4f1684bac52c566e0b43.png][]

### **编码** ###

/**
         * 二分查找基础版
         *
         * @param arr    查找升序数组
         * @param target 目标值
         * @return 找到返回索引
         * 找不到返回-1
         */
        public static int binarSearchBasic(int[] arr, int target) {
            //设置初值的索引
            int i = 0;
            int j = arr.length - 1;
    
            //循环
            while(i<=j){  //在范围内
    		   int mid=(i+j)/2;
                //获取中间值
                if(target<arr[mid]){ //目标左边
                    j=mid-1;
                }else if(arr[mid]<target){//目标右边
                    i=mid+1;
                }else { //找到了
                    return mid;
                }
            }
            return -1;
        }

### 五、图示所示-改进版 ###

**问题：对应（i+j)/2 有没有问题 ？**

> 如果超过正整数最大值表示的范围，由正变负，发生错误！！

@Test
        public void main() {
            int i = 0;
            int j = Integer.MAX_VALUE - 1;
            int m = (i + j) / 2;
            System.out.println(m);  //1073741823
            //如果目标在右侧
            i = m + 1;
            System.out.println(i);  //1073741824
            System.out.println(j); //2147483646
            System.out.println(i+j); // -1073741826
    //        m = (i + j) / 2;
            m = (i + j) >>>1;   //1610612735
    
            System.out.println(m);  //-536870913
            //此时发生错误：超过正整数能表示的范围，由正变负。
            //二进制数：
            //把java二进制数最高位为符号位，代表: -1073741826
            //不把二进制数最高位为符号位，代表：3221225470
        }

> 修改：无符号右移1位 >>> 1 ； (可以使更多的语言)
> 
> m = (i + j) >>>1

**查找target=13**

![9ca0fe5bff4f4e08a714d0d5c21ad40f.png][]

![50c07b970ed041cea0137af938f538fe.png][]

![83595dca613e44f794b9debdcb74247d.png][]

![de3362c3892b49f686f167d4c27dafb0.png][]

![5b5b6386ca4948aeb85f75e8345c9b6a.png][]

![7f8cab3f9e594cc5aa5ff3715ad6a5bd.png][]

![87a6595d6fbd46d19fa6f1307fb83c53.png][]

### **编码** ###

/**
         * 二分查找改动版
         *
         * @param arr    查找升序数组
         * @param target 目标值
         * @return 找到返回索引
         * 找不到返回-1
         */
        public static int binarSearchUpdate(int[] arr, int target) {
            //设置初值的索引
            int i = 0;
            int j = arr.length ; //第1处
    
            //循环
            while(i<j){  //第2处
                //中间值
                int mid=(i+j)>>>1;
                //获取中间值
                if(target<arr[mid]){ //目标左边
                    j=mid;    //第3处
                }else if(arr[mid]<target){//目标右边
                    i=mid+1;
                }else { //找到了
                    return mid;
                }
            }
            return -1;
        }

[Link 1]: https://so.csdn.net/so/search?q=%E6%8A%98%E5%8D%8A%E6%9F%A5%E6%89%BE&spm=1001.2101.3001.7020
[dbc8b4185b3e4d2690bdd0844bc103bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/d853bb6c9a0943f6a0d5291eb07e66b0.png
[7901d1abd25d43c6a26a886b4ce9ecdb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c1fb30b84faf4571838e1e4dbef709e5.png
[c06edbfda4814cc388ff567ef684b00d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ac7c9c14185648dbbaf3eb3690e30419.png
[50bd93e069a6403a8cfb5742b1d5d795.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/48f25f21dd1346b583ea80956430e100.png
[847ec344fd0c4e1991f7b501d302961e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ae8ab38d56f84e51b2b79bad7875237e.png
[a88af61a07aa4f1684bac52c566e0b43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/d183ffa9c43240e69a481b0b4fbba4be.png
[9ca0fe5bff4f4e08a714d0d5c21ad40f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/2181732830174a649290ec598c5c67c6.png
[50c07b970ed041cea0137af938f538fe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/04eb5e856b2947609cc8cc58fb2f5306.png
[83595dca613e44f794b9debdcb74247d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/310f280bffa04a3a85bb47696268edfb.png
[de3362c3892b49f686f167d4c27dafb0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/3405e59fcfcf4cc48d792949525f9ff4.png
[5b5b6386ca4948aeb85f75e8345c9b6a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/28e6d2c690ac4319b075c8129d3e998c.png
[7f8cab3f9e594cc5aa5ff3715ad6a5bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/e86666152ed44e5fb68ed8982e5d53b3.png
[87a6595d6fbd46d19fa6f1307fb83c53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a0227a70c71740c7aee86199202d27ca.png