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

二分查找算法

请对一个有序数组进行二分查找，{1, 8, 10, 89, 1000, 1024}，输入一个数看看该数组是否存在次数，并且求出下标，如果没有就提示没有这个数

{1, 8, 10, 89, 89, 89, 1000, 1024}当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如 89

二分算法的思路分析

1. 首先确定该数组的中间的下标mid = (left + right) / 2
2. 然后让需要查找的数 findVal 和 arr[mid] 比较
   • findVal > arr[mid]，说明你要查找的数在 mid 的右边，因此需要递归的向右查找
   • finVal < arr[mid]，说明你要查找的数在 mid 的左边，因此需要递归的向左查找
   • findVal == arr[mid]说明找到，返回
3. 结束递归
   • 找到就结束
   • 递归完整个数组，仍然没有找到 findVal，也需要结束递归， left > right

代码实现

package com.ke.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找，数组必须是有序的
 *
 * @program: data-structure-algorithm
 * @author: ke
 * @create: 2021-12-12 16:57
 **/
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 89, 89, 1000, 1024};
        int resIndex = binarySearch(arr, 0, arr.length - 1, 89);
        // 结果下标=3
        System.out.println("结果下标=" + resIndex);
        List<Integer> list = binarySearch2(arr, 0, arr.length - 1, 89);
        // 结果下标集：[3, 4, 5]
        System.out.println("结果下标集：" + list);
    }

    /**
     * 二分查找
     *
     * @param arr     数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 查找的值
     * @return 找到就返回下标，否则返回 -1
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        // 当left > right时，说明递归整个数组没有找到
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];

        // 向右递归
        if (findVal > midVal) {
            return binarySearch(arr, mid + 1, right, findVal);
        }
        // 向左递归
        else if (findVal < midVal) {
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }

    /**
     * 二分查找找到数组中所有符合查找值的下标
     * 思路：
     * 1. 在找到 mid 索引值，不要马上返回
     * 2. 向 mid 索引值的左边扫描，将所有满足查找值的元素的下标加入到集合ArrayList中
     * 3. 向 mid 索引值的右边扫描，将所有满足查找值的元素的下标加入到集合ArrayList中
     * 4. 将ArrayList返回
     *
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
        // 当left > right时，说明递归整个数组没有找到
        if (left > right) {
            return new ArrayList<>();
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];

        // 向右递归
        if (findVal > midVal) {
            return binarySearch2(arr, mid + 1, right, findVal);
        }
        // 向左递归
        else if (findVal < midVal) {
            return binarySearch2(arr, left, mid - 1, findVal);
        } else {
            List<Integer> resIndexList = new ArrayList<>();
            // 向左扫描
            int temp = mid - 1;
            while (true) {
                // 最左边或发现有一个不等于查找值
                if (temp < 0 || arr[temp] != findVal) {
                    break;
                } else {
                    resIndexList.add(temp);
                    // 继续扫描下一位
                    temp -= 1;
                }
            }
            // 存入中间值
            resIndexList.add(mid);
            temp = mid + 1;
            // 向右扫描
            while (true) {
                // 最右边或发现有一个不等于查找值
                if (temp > arr.length - 1 || arr[temp] != findVal) {
                    break;
                } else {
                    resIndexList.add(temp);
                    // 继续扫描下一位
                    temp += 1;
                }
            }
            return resIndexList;
        }
    }

}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

运行结果
结果下标=3
结果下标集：[3, 4, 5]
1
2
3