欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

写一个简单的二分查找

程序员文章站 2022-07-12 09:35:00
...
二分查找的概念:
二分查找是算法里面比较简单的算法,很多人接触算法都是从二分查找开始入门的,
二分查找也叫折半查找,
它是运用分治策略的典型例子。折半查找方法适用于不经常变动而查找频繁的有序列表。
所以它在有序数组中经常被使用到。

经过分析,总结出二分查找的编写需要注意的几个点。

1. 计算出最低的索引:0

2. 计算出最高的索引:length -1 

3. 计算出中位数的索引: (最高 + 最低) /  2

4. 如果要查找的数大于中位数:则把最低位的索引改变成 中位数的索引 + 1 

5. 如果要查找的数小于中位数: 则把最高位的索引改变成 中位数的索引 - 1

6. 如果要查找的数刚好等于中位数: 则直接break

7. 如果低位大于了高位,则证明没有找到需要找到的数

下面就为最简单的二分查找提供一个代码实例:注意给到的数组必须是有顺序的,不能是乱序的

/*
    这是一个二分超找的简单实例
    二分查找的概念:
    二分查找是算法里面比较简单的算法,很多人接触算法都是从二分查找开始入门的,
    二分查找也叫折半查找,
    它是运用分治策略的典型例子。折半查找方法适用于不经常变动而查找频繁的有序列表。
    所以它在有序数组中经常被使用到。
 */


public class TwoSearch {

    public static void main(String[] args) {

        // 随便去指定一个数组
        int[] number = {1,2,3,11,22,33,44,55,66,77};



        //随便指定一个需要查找的数据
        int findValue = 3;

        // 计算最低位的索引
        int low = 0;

        // 计算最高位的索引
        int high = number.length - 1;

        // 计算中位的索引
        int mid = (low + high) / 2;

        System.out.println((low + high) / 2);


        // 先对需要查找的值是否在范围里面进行判断
        if (findValue > number[high] || findValue < number[low]){
            System.out.println("所需要查找的值不存在");
            return;
        }

        while (low <= high){
            // 首先判断要找的值是否等于中位数,如果刚好等于就直接break
            if (number[mid] == findValue){
                System.out.println("找到了值,下标是" + mid);
                break;
            }

            //大于中位数的情况,对最低的索引进行初里,中位数索引+1
            if(findValue > number[mid]){
                low = mid + 1;
                mid = (low + high) / 2;
                continue;
            }


            //小于中位数的情况,对最高的索引进行初里,中位数索引-1
            if (findValue < number[mid]){
                high = mid - 1;
                mid = (high + low)/ 2;
            }
        }
    }
}

相关标签: 技术 算法