【二分查找详解外加递归写法】附有全部代码

二分查找

二分查找：在有序（升序或降序）的集合上，才能使用二分查找。

二分查找的思路：

在一个有序数组中查找一个数 n,我们可以把 n 与 数组的中间元素(mid)不断的去比较，

​ 若 n < arr[mid], 说明数字 n 在左区间，则数组右侧的索引变为 mid-1，左侧的索引加1

​ 若 n > arr[mid], 说明数字 n 在右区间，则数组左侧的索引变为 mid+1，右侧的索引加1

​ 当 ==n = arr[mid]==时，在数组中找到了这个数字

数组的左侧索引(left) 大于 右侧索引(right),就把这个数组都找了一遍，没有找到这个数。

循环条件是 left <= right,为什么需要加等于呢，当下标都相等时，数组内还有一个元素。

图解：

查找数字11

第一步：

11 > arr[mid] ,

第二步：数字在数组 的右区间，left = mid +1;

就这样一直进行比较

---

代码如下：

import java.util.Scanner;

public class PublicTwoFind {
    
    public static void main(String[] args) {
    
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[]{
    1,2,3,4,5,6,7,8,9,10,11};
        twoFind(arr,0,arr.length-1,11);
        int find = 1;
        int left = 0;  //数组最左侧元素的下标
        int right = arr.length-1; //数组最右侧元素的下标
        while(left <= right){
       //终止条件
            int mid = (left + right)/2; //得到数组中间元素下标
            if(find < arr[mid]){
    
                right = mid - 1;
            }else if(find > arr[mid]){
    
                left = mid + 1;
            }else {
     //find == arr[mid]
                System.out.println("找到了，下标是：" + mid);
                break;
            }
        }
        if(left > right){
    
            System.out.println("找不到这个数");
        }
    }

    /**mid 表示中间元素的下标 *终止条件是 当left > right,表示没有这个数，结束方法 * 当num == arr[mid],表示找到了这个数，打印mid * 拆分问题：比较num 和arr[mid] 的大小， * 若 num > arr[mid],则在[mid + 1,right]的数组范围内查找，此时mid+1 就是新的left * 或 num < arr[mid],则在[left,mid -1]的数组范围内查找,此时mid -1 就是新的right； * 接着在新的数组范围内继续比较，直到遇到终止条件 * *假设查找数字的函数已经写好，我们只需要在判断num是否大于中间元素，然后调用函数，就可以得到这个数字下标 * *@param arr 查找的数组 * @param left 数组的右侧下标 * @param right 数组的左侧下标 * @param num 查找的数字 */
    //递归的写法
    public static void twoFind(int[] arr,int left,int right,int num){
    
        if(left > right){
    
            System.out.println("没有这个数");
            return;
        }
        int mid = (left + right)/2;
        if(num == arr[mid]){
    
            System.out.println("1找到了，下标是：" + mid);
            return;
        }else if(num > arr[mid]){
    
            twoFind(arr,mid + 1,right,num);
            return;
        }
        twoFind(arr,left,mid - 1,num);
    }
}

---

要是对大家有所帮助的话，请帮我点个赞吧。