Java算法(十二):【数据结构与算法】 十大排序 之 二分查法 && 二分查法实现详细流程图分析 && 实现源码实例

发布时间:2023年12月18日

二分查找

二分查找

  • 二分查找就是返回有序序列中,需要查找的元素索引,无则-1。

在这里插入图片描述

在这里插入图片描述

    需求:二分查找:手写实现数组元素的查找,存在返回索引,无则返回 -1;
        实现思路:(前提是有序的序列)
                1、 如果不是有序的数组,我们先排序(选择、冒泡)任意;
                2、 创建三个指针,分别为:第一个元素指针和最后一个指针以及中间元素的指针
                3、 确保条件成立(min < max),方可继续执行查找,否则没有
                4、 判断是否相等,相等返回索引,否则返回 -
4.1 代码示例 (这里采用乱序数组)
public class DichotomyFind {
    public static void main(String[] LiuJinTao) {
        
        // 创建一个数组,很明显,这我故意设置为乱序的,目的是为了复习排序
        int [] arr = {11, 33, 55, 22, 44, 99, 77, 66, 88, 100};
        // 这里为了清晰明了,这里我使用方法来进行封装
        /**
         *  数组排序
         */
        SelectSortHandle(arr);
        /**
         *  二分查找
         */
        int result = DichotomyFindHandle(arr, 100);
        System.out.println(result);
        

    }
    
    
    /**
     * 二分查找
     * @param arr
     * @param element
     * @return
     */
    private static int DichotomyFindHandle(int [] arr, int element) {
        // 2. 创建指针
        int min = 0;
        int max = arr.length - 1;
        int mid;
        // 3. 根据条件是否成立,决定是否查找
        while (min <= max) {
            mid = (min + max) / 2;
            // 4. 判断是否相等,注意的是记得调整min和max的指针位置
            if (element < arr[mid]) {
                max = mid - 1;
            } else if (element > arr[mid]) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    
    
    /**
     * 选择排序数组
     * @param arr
     */
    private static void SelectSortHandle(int[] arr) {
        // 1. 二分查找前提处理
        for (int i = 0; i < arr.length - 1; i++) {
            // 这里选择排序
            for (int j = i + 1; j < arr.length; j++) {
                // 下标为 0 开始,向后面元素进行判断比较。
                if (arr[i] > arr[j]) {
                    // 当前面的元素大于后面的元素,就交换位置,然后从下标 1 开始,以此类推
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        // 查看排序结果 → 将 int 数组 格式化为 String类型输出
        System.out.println(Arrays.toString(arr)); //[11, 22, 33, 44, 55, 66, 77, 88, 99]
    }
}
文章来源:https://blog.csdn.net/Forever_Hopeful/article/details/135070525
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。