[Detailed explanation of binary search plus recursive writing method] with all the code

二分查找

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

二分查找的思路：

在一个有序数组中查找一个数 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);
    }
}

---

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