java-有序数组二分查找法_java给定一组有序序列,用随机化二分查找的方法查找某元素x。提示:随机化二分查找

问题1：假设有一个有序数组arr[] = {1,3,4,6,9,11,15}，用二分的方式找其中的数值11。
二分的意思就是把数组一分位二，当前数组的中点位置的下标为：(0 + 7)/2 = 3 的位置；
分为a1数组{1,3,4,6} （下标从 0 - 3）和 a2数组{9,11,15}（下标从 4 - 6），显然a1数组的终点6小于要查找值11，所以a1数组中不可能存在，
再次二分a2数组,此中点位置的下标(4+7)/2=5，分为数组b1{9,11}（下标从4 - 5）， 和 数组b2{15}（下标从 6 - 6），b1的终点位置值等于11，直接取出。

public class BinarySearch {
   
    public static void main(String[] args) {
   
        int[] arr = {
   1,3,4,6,9,11,15};
        System.out.println(find(arr,11));
    }
    /**
     * 二分查找num 是否存在 数组arr中
     * @param arr
     * @param num
     * @return
     */
    public static boolean find(int[] arr,int num){
   
        if(null == arr || arr.length == 0){
   
            return false;
        }
        // 先定义左右边界，因为无法直接去掉一半，所以先给定左边界为 0 有边界为arr.length-1
        int L = 0;
        int R = arr.length - 1;
        //while 实现每次取一半查找
        while (L < R){
   
            //定义中点位置，
            int mid = (L + R)/2;
            if(arr[mid] == num){
    // 如果等于num 说明已找到 ，返回true
                return true;
            }
            // 上面判断跳过，说明arr[mid] 不等于 num,
            //判断 中点位置 arr[mid] 如果 大于 num，说明 右边界 mid - R 位置的值 大于 num，num 存在 左边界 L - mid 位置
            // 将右边界 R 设置为 mid-1
            else if(arr[mid] > num){
   
                R = mid - 1;
            }
            //中点位置 arr[mid] 如果 小于 num，说明 左边界 L - mid 位置 小于 num，num 存在 右边界 mid - R 位置的值
            // 将 左边界 L 的 位置 设置为 mid+1.
            else{
   
//            if(arr[mid] < num){
   
                L = mid + 1;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49