算法之二分查找法

需求描述：

        在有序数组A内，查找值target

        如果找到返回索引

        如果找不到返回-1

算法实现描述

        前提条件：给定一个含有n个元素的有序数组A，满足A0≤A1≤A2≤···An-1，一个待查值target

        实现步骤：        1、创建i = 0, j = n - 1;

                                   2、如果i > j，结果查找，没找到

                                   3、设置m = floor((i+j) / 2),m为中间索引，floor是向下取整(≤(i + j) / 2的最小整数)

                                   4、如果target < Am 设置 j = m - 1，跳到第二步

                                   5、如果Am < target 设置 i = m + 1, 跳到第二步

                                   6、如果Am = target，结束查找，找到了

代码实现

    /***
         * 二分查找法实现
         * @param args 数据
         * @param target 查找目标
         * @return 找到返回索引
         *         找不到返回-1
     */
    public static int binarySearchBasic(int[] args, int target) {
        int i = 0, j = args.length - 1;//设置指针和初始值
        while (i <= j) {//范围内有东西
            int m = (i + j) / 2;
            if (target < args[m]) {//目标在左边
                j = m-1;
            } else if (args[m] < target){//目标在右边
                i = m + 1;
            } else {
                return m;//找到数据的id
            }
        }
        return -1;
    }

原文地址：https://blog.csdn.net/Dragonlongbo/article/details/143030626

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！