程序员必会的查找算法——二分查找（折半查找）

蔚落 2023-02-18 08:30 27阅读 0赞

之前的发布了许多排序算法（后面还会介绍堆排序）,从今天开始学习一下查找算法。今天要分享的是每个程序员必须会的查找算法——二分查找（也称为折半查找）。**这里要知道二分查找需要一个前提，那就是二分查找是基于有序序列的。**

**二分查找基本思路：  
每次取出序列中的中间值，将需要查找的元素与之比较。这里有三种情况。  
一、如果该元素比中间值小就继续向左查找。  
二、恰好序列中的中间值正是要查找的元素。  
三、如果该元素比中间值大就继续向右查找。  
（在向左或右查找时，又需要取出左序列或右子序列的中间值作比较，直至找到该元素）**

由于这个过程不难理解，所以直接给出完整的代码。

/**
         * 
         * @param arr 待排序序列（数组）
         * @param left 起始下标
         * @param right 结束下标
         * @param value 要查找的元素
         * @return
         */
        public static int binarySearch(int[] arr,int left,int right,int value){
        
            //递归结束条件
            //表示没有找到需要查找的元素
            if (left > right){
        
                return -1;
            }
            //得到中间值
            int mid = (left + right) / 2;
            int midValue = arr[mid];
            
            if (value > midValue){
        
                return binarySearch(arr,mid + 1,right,value);//右递归
            }else if (value < midValue){
        
                return binarySearch(arr,left,mid - 1,value);//左递归
            }else {
        
                return mid;//找到了该值
            }
        }

至此二分查找的基本使用就讲完了，但是以上代码也有一些BUG，细心的你也许发现了。当我们序列中存在多个需要查找的元素时，上面代码却只能返回给我们一个该元素的位置，所以明显是不对的。所以对以上代码改进为：

/**
         *
         * @param arr 待排序序列（数组）
         * @param left 起始下标
         * @param right 结束下标
         * @param value 要查找的元素
         * @return
         */
        public static List binarySearch02(int[] arr,int left,int right,int value){
        
            //递归结束条件
            //表示没有找到需要查找的元素
            if (left > right){
        
                return null;
            }
            //获取中间值
            int mid = (left + right) / 2;
            int midValue = arr[mid];
            if (value > midValue){
        
                return binarySearch02(arr,mid + 1,right,value);//向右递归
            }else if (value < midValue){
        
                return binarySearch02(arr,left,mid - 1,value);//向左递归
            }else {
        
                List<Integer> list = new ArrayList<Integer>();//定义一个集合，用来存放查找多个元素的位置
                //temp存放mid也就是查找元素的前一个位置
                int temp = mid - 1;
                //这个循环会一直向左查找是否要查找的元素存在多个
                while (true){
        
                    if (temp < 0 || arr[temp] != value){
        
                        break;
                    }
                    list.add(temp);
                    temp --;
                }
                list.add(mid);//mid，作为查找元素是第一个被找到的，理应放入集合中
                //temp存放mid也就是查找元素的后一个位置
                temp = mid + 1;
                //这个循环会一直向右查找是否要查找的元素存在多个
                while (true){
        
                    if (temp > arr.length -1 || arr[temp] != value){
        
                        break;
                    }
                    list.add(temp);
                    temp ++;
                }
                return list;
            }
        }

到此二分查找算法就算结束了，可以看到，改进的思路就是当找到需要查找的元素时，在此基础上还需要判断它的前面和后面是否也有该元素，因为是有序序列嘛，如果存在同一个元素肯定是相邻的。

总结：二分查找思想还是很简单的，代码实现也不复杂。这里的二分查找是采用递归实现的，当然也可以不使用递归，总之，思想都是一样的，所以暂时就不再赘述了，需要的话后面再补吧。