频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
[Java源码]排序数组二分法(折半)查找
2013-03-09 12:57:11           
收藏   我要投稿
对于已排序的数组,二分法是一种很简单、有效的查找方式,算法复杂度为O(log2n);

代码:

[java]  

package alg;  

  

public class Bisection {  

  

    public static int bisectionSearch(int value,int[] array) {  

        int minIndex = 0;  

        int curIndex = 0;  

        int maxIndex = array.length - 1;  

        int count = 0;  // 用于循环次数记数  

        int result = -1;  

          

        if (value == array[maxIndex]) {  

            result = maxIndex;  

        } else if (value == array[minIndex]) {  

            result = minIndex;  

        } else {  

            while(true) {  

                // 如果两者相同或相邻,由于二者的值(除首次)均来自于已与value比较不等的值,因此数组中没有该值。  

                if (2 > maxIndex - minIndex) {  

                    result = -1;  

                    break;  

                }  

                curIndex = minIndex + (maxIndex - minIndex) / 2;  

                if (array[curIndex] == value) {  

                    result = curIndex;  

                    break;  

                } else if (array[curIndex] < value) {  

                    minIndex = curIndex;  

                } else {  

                    maxIndex = curIndex;  

                }  

                count++;  

            }  

        }  

        System.out.println("loops = " + count);  

        return result;  

    }  

      

    public static void main(String[] args) {  

        int num = 1000;  

        int value = 0;  

        int[] array = new int[num];  

        for (int i = 0; i < num; i++) {  

            array[i] = i;  

        }  www.2cto.com

        System.out.println("value = " + value + " at index " + bisectionSearch(value,array) + " of array.");  

    }  

}  

Author:Pirate Leo

blog:https://blog.csdn.net/pirateleo

email:codeevoship@gmail.com

点击复制链接 与好友分享!回本站首页
相关TAG标签 二分法 数组 源码
上一篇:java多线程中synchronized关键字的用法
下一篇:设计模式--结构模式--装饰模式--Java
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站