冒泡排序结合二分查找寻找数字

文章目录

• • 总体思路：
  • 冒泡排序
  • • 思路
    • 优化
  • 二分查找
  • • 二分查找思路：
    • 小细节

总体思路：

要想查找某一个数字，我们最先想到的就是二分查找，但是二分查找有一个前提，数组的元素必须要是有序的，所以查找数字之前要进行数字排序

冒泡排序 思路

冒泡排序是十分经典的排序方法，首先要知道有n个数字就意味着有n-1趟排序，趟数也决定了后面要进行的判断的次数，再进行判断每一趟排序要判断是否满足升序的条件，要是满足就进行交换前后的数字即可

public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flg = true;
                }
            }
  
         }
    }

优化

要是数组的元素已经是升序的，这样子的运行效率就不会很好了，所以可以设一个标示量flg，通过判断它的状态，进行代码的优化

 public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flg = false;//每一趟都要将flg置为false,所以要将flg=false放第一层for循环里面
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flg = true;
                }
            }
            if (flg == false) {
                return;     // 要是flg还是等于false，就是没交换，说明都满足升序，所以直接return或者break结束最外面的for循环
            }
        }

    }

在解决了数组元素有序性的问题之后，我们就可以开始写二分查找了

二分查找 二分查找思路：

给定一个数组，首先求出数组的左右端数字的下标使之分别为l r，接着求出数组的中间元素arr[mid]

接着输入要查找的数字key

1.当arr[mid]>key时，说明key出现在arr[mid]左边，所以需要将 右下标r 进行左移，左移至mid-1处，进入循环再判断，直至 arr[mid]等于key或者 l 与 r 相等退出循环

2.当arr[mid]

3.要是数组中不存在要查找的数字，就直接返回一个-1

小细节

在求中间元素的下标时，可以使用mid=（l+r）/2 ,但是规定mid是int类型的，有可能有超出int表示的范围，使用可以写成mid=l+(r-l)/2 的形式来避免超出int的范围

原理如图，就是将r多出l的部分一切为二，将其加到 l 上即可使两者一样大

最终代码如下

//冒泡排序
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flg = false;//每一趟都要将flg置为false
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flg = true;
                }
            }
            if (flg == false) {
                return;     // 要是flg还是等于false，就是没交换，说明都满足升序，所以直接return或者break结束最外面的for循环
            }
        }

    }

    //二分查找
    public static int binarySearch(int[] arr, int key) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] > key) {
                r = mid - 1;
            } else if (arr[mid] < key) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 6, 3, 12, 45, 4};
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {  //多组输入要查找的数字
            int key = scanner.nextInt();
            bubbleSort(arr);//进行冒泡排序
            System.out.println(Arrays.toString(arr));//输出排序后的数组
            System.out.println(binarySearch(arr, key));
        }
    }