二分查找（递归+非递归）

悠悠 2022-12-07 11:56 222阅读 0赞

### 文章目录 ###

*  二分查找
 *  递归实现
 *  非递归实现
 *  附加问题：安全防溢出的两整数平均值算法
 *  相关一些题目
 *   *  题一：无目标值，返回插入序号

# 二分查找 #

二分查找是一种查询效率非常高的查找算法。又称折半查找。

起初在数据结构中学习递归时实现二分查找，实际上不用递归也可以实现，毕竟递归是需要开辟额外的空间的来辅助查询。本文就介绍两种方法

*  优缺点  
    优点是比较次数少，查找速度快，平均性能好；

其缺点是要求待查表为有序表，且插入删除困难。

因此，折半查找方法适用于不经常变动而查找频繁的有序列表。  
使用条件：查找序列是顺序结构，有序。

# 递归实现 #

//二分查找递归实现
        public static int binaryserach_recursion(int arr[],int aimnum,int low,int high){
        
            if (aimnum<arr[low] || aimnum > arr[high] || low > high){
        
                return -1;
            }
            int middle=(high+low)/2;
            if (aimnum > arr[middle]){
        
                return binaryserach_recursion(arr,aimnum,middle+1,high);
            }else if (aimnum < arr[middle]){
        
                return binaryserach_recursion(arr,aimnum,low,middle-1);
            }else {
        
                return middle;
            }
        }

# 非递归实现 #

为何有了递归我们还要去看非递归呢？因为我们知道每当我们调用一个函数JVM会在会在虚拟机栈中创建一个栈帧，那么当我们递归次数不多当然看不出来，当递归的次数过多，那么我们就会撑爆虚拟机栈导致栈溢出。

//二分查找非递归实现
        public static int binarySearch_loop(int arr[],int aimnum,int low,int high){
        
            if (aimnum<arr[low] || aimnum > arr[high] || low > high){
        
                return -1;
            }
            int middle=0;
            while (low <= high){
        
                middle=(low+high)/2;
                if (arr[middle] < aimnum){
        
                    low = middle+1;
                }else if (arr[middle] > aimnum){
        
                    high=middle-1;
                }
                else return middle;
            }
            return -1;
        }

*  注意点：

1.  while (low <= high)：我们用的小于等于，而不是小于，这是保证一种情况可能少比一次，大家可以仔细思考。
2.  int middle=(high+low)/2;：这里会有可能middle是int类型可能发生溢出的风险，这个我们在下面细讲。
3.

# 附加问题：安全防溢出的两整数平均值算法 #

我们在前面看到我们每次算两个数的平均数数时使用的是int middle=(low+high)/2; 这个在我们int范围内当然没事，但是当我们数据过大会导致溢出问题！

*  特别对于二分查找我们可以这样修改

int right=(high-low+1)/2+low

*  如果对于平均，有一种专门的防溢出算法

public static int mean(int a, int b){
        
        return (x & y) + ((x ^ y) >> 1);
    }

# 相关一些题目 #

## 题一：无目标值，返回插入序号 ##

*  题目描述：给定一个排序好的数组和目标值。如果在数组中找到目标值，则返回目标值索引号。如果在数组中找不到目标值，则返回可以插入的索引下标。  
    这个题目主要是我们最后肯定会返回一个索引，就是最后查到的索引，但是这个索引是目标值索引还是可插入索引不知道，这个时候我们可以将它抽象成一个类，两个属性：一个是索引值，一个是布尔值（是否是目标值）

class IndexNode{
        
        int index;
        Boolean flag;
    
        public IndexNode(int index, Boolean flag) {
        
            this.index = index;
            this.flag = flag;
        }
    }
    public class BinarySerach_withNode {
        
    
    
        public static IndexNode binarySerach(int arr[],int aimnum){
        
            IndexNode pos=new IndexNode(-1,false);
            int low=0;
            int high=arr.length-1;
            int middle=0;
            while (low <= high){
        
                middle=(high-low+1)/2+low;
                if (aimnum > arr[middle]){
        
                    low=middle+1;
                }else if (aimnum < arr[middle]){
        
                    high=middle-1;
                }else {
        
                    pos.index=middle;
                    if (arr[middle]==aimnum){
        
                        pos.flag=true;
                    }else {
        
                        pos.flag=false;
                    }
                    break;
                }
            }
            return pos;
        }
    
    
        public static void main(String[] args) {
        
            int arr[]={
        1,2,3,4,5,67,75,88,99};
            IndexNode pos=binarySerach(arr,0);
            System.out.println(pos.index );
            System.out.println(pos.flag);
        }
    }