美文网首页
java二分查找

java二分查找

作者: 择夕_ | 来源:发表于2017-12-02 22:44 被阅读0次

对于程序猿或者程序媛来讲,二分查找貌似并不陌生主要是循环遍历一个有序的数组找到你想要的元素。二分查找gitHub,具体图解如下:

image

当时我的想法是这就是个简单的递归算法,每次查询array[array.length/2] == number

判断第ary.length/2个元素的值是否与number相等,并返回arry中的位置。废话不多说了,直接上代码

    //在ary中通过二分查找的方式找到对应数字在ary中的位置
    public static int getOneNumberBayHalf(int [] ary,int number,int start, int end){
        if(start> end)
            return  -1;
        int mid = start +(end -start)/2;
        if (number == ary[mid]) {
            System.out.print("数字:" + number+"的位置在从ary中的第"+mid+"位");
            return mid;
        }
        if (number < ary[mid]){
            return getOneNumberBayHalf(ary,number,start,mid-1);
        }
        //if (number > ary[mid])
        else {
            return getOneNumberBayHalf(ary,number,mid+1,end);
        }
    }

递归算法如果没设计好推出逻辑很容易出现stackoverflow。确实是这样,我一开始把出口逻辑写错了。如下(以下是典型错误示范,所以大家一定要注意):

    public static int binarySearch(int[] array, int target) {
        int low = 0, high = array.length - 1;
        while (low < high) {
            int mid =(high - low) / 2;
            if (target == array[mid]) {
                return mid;
            } else if (target > array[mid]) {
                low = mid + 1;
            } else if (target < array[mid]) {
                high = mid;
            }
        }
        return -1;
    }

执行的时候直接死循环了,毕竟是干QA的直接发现逻辑有问题于是被我优化了一下,如下:

    public static int binarySearch(int[] array, int target) {
        int low = 0, high = array.length - 1;
        while (low < high) {
            // 下面代码一定注意,否则会进入死循环
            // int mid =(high - low) / 2;
            // 正确写法如下
            int mid =low + (high - low) / 2;
            if (target == array[mid]) {
                return mid;
            } else if (target > array[mid]) {
                low = mid + 1;
            } else if (target < array[mid]) {
                high = mid;
            }
        }
        return -1;
    }

希望看完这篇文章的QA同学们以后都要注意一下开发的写法,尤其是对循环、判断、递归出口等,一定要注意一下,及时发现问题并指正!

相关文章

  • 二分查找

    概念二分查找又叫折半查找,从排序数组中查找元素的位置。 图示二分查找 Java实现 复杂度T(n)=T(n/2)+...

  • 二分查找代码框架

    1.基本的二分查找 2.寻找左侧边界的二分查找 3.寻找右侧边界的二分查找 4.说明 这是一个Java实现的二分查...

  • 面试知识点

    排序冒泡排序快速排序选择排序插入排序二路归并 查找二分查找 排序和查找的java实现 java语言Java字符串字...

  • 二分查找(折半查找)

    二分查找源代码(Java) package sort; public class serach { public ...

  • Java数据结构与算法:查找算法

    在java中,我们常用的查找有四种: 顺序(线性)查找 二分查找/折半查找 插值查找 斐波那契查找 1、线性查找 ...

  • Java实现二分查找

    Java实现二分查找 二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对比...

  • 二分查找

    定义 过程 要求 算法复杂度 Java代码实现 定义   二分查找也称折半查找(Binary Search),它是...

  • 四大查找算法

    在Java中,常用的查找算法有以下四种: 顺序查找; 二分查找; 插值查找; 斐波那契查找; 欢迎大家关注我的公众...

  • python二分查找算法

    文章概述 二分查找法介绍 简单查找与二分查找对比 二分查找  二分查找算法主要思想:在有序列表中查找指定元素,先从...

  • 数据结构和算法--二分查找

    二分查找 二分查找的思想 二分查找(Binary Search)算法,也叫折半查找算法。 二分查找针对的是一个有序...

网友评论

      本文标题:java二分查找

      本文链接:https://www.haomeiwen.com/subject/qduobxtx.html