java 二分查找算法

二分查找又称折半查找,它是一种效率较高的查找方法。

将数列按有序(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。 它可以明显减少比较次数,提高查找效率。但是,表中的数据元素必须有序,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

步骤描述

① 首先确定整个查找区间的中间位置 mid = ( left + right )/ 2;

② 用待查关键字值与中间位置的关键字值进行比较;

若相等,则查找成功

若大于,则在后(右)半个区域继续进行折半查找

若小于,则在前(左)半个区域继续进行折半查找

③ 对确定的缩小区域再按折半公式,重复上述步骤。

最后,得到结果:要么查找成功, 要么查找失败。折半查找的存储结构采用一维数组存放。

折半查找算法举例

        public static void main(String[] args) { 
            int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};   
            System.out.println(binSearch(srcArray, 0, srcArray.length - 1, 81));  
        } 

        // 二分查找递归实现   
        public static int binSearch(int srcArray[], int start, int end, int key) {   
            int mid = (end - start) / 2 + start;   
            if (srcArray[mid] == key) {   
                return mid;   
            }   
            if (start >= end) {   
                return -1;   
            } else if (key > srcArray[mid]) {   
                return binSearch(srcArray, mid + 1, end, key);   
            } else if (key < srcArray[mid]) {   
                return binSearch(srcArray, start, mid - 1, key);   
            }   
            return -1;   
        }

评论

h
hw_7864

⭐️ Admin快速开发: https://show.cool-admin.com/

赞 0
h
hw_7864

⭐️ 官方文档: https://cool-js.com

赞 0
h
hw_7864

⭐️ chatgpt在线体验: https://cool-js.com/ai/chat-vip/index.html?r=helloworld

赞 0