文档章节

Java算法之 二分搜寻法 ( 搜寻原则的代表)

郑加威
 郑加威
发布于 2017/04/18 15:50
字数 483
阅读 9
收藏 1

二分搜寻法 ( 搜寻原则的代表)

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

2.二分查找要求:(1)必须采用顺序存储结构 (2).必须按关键字大小有序排列

3.原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前 面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。

4.实现:二分查找的实现用递归和循环两种方式

5.代码:


 public class BinarySearch {
     /*
      * 循环实现二分查找算法arr 已排好序的数组x 需要查找的数-1 无法查到数据
      */
     public static int binarySearch(int[] arr, int x) {
         int low = 0;   
         int high = arr.length-1;   
         while(low <= high) {   
             int middle = (low + high)/2;   
             if(x == arr[middle]) {   
                 return middle;   
             }else if(x <arr[middle]) {   
                 high = middle - 1;   
             }else {   
                 low = middle + 1;   
             }  
         }  
         return -1;  
     }
     //递归实现二分查找
     public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){    
            int midIndex = (beginIndex+endIndex)/2;    
            if(data <dataset[beginIndex]||data>dataset[endIndex]||beginIndex>endIndex){  
                return -1;    
            }  
            if(data <dataset[midIndex]){    
                return binarySearch(dataset,data,beginIndex,midIndex-1);    
            }else if(data>dataset[midIndex]){    
                return binarySearch(dataset,data,midIndex+1,endIndex);    
            }else {    
                return midIndex;    
            }    
        }   
 
     public static void main(String[] args) {
         int[] arr = { 6, 12, 33, 87, 90, 97, 108, 561 };
         System.out.println("循环查找:" + (binarySearch(arr, 87) + 1));
         System.out.println("递归查找"+binarySearch(arr,3,87,arr.length-1));
     }
 }

 

© 著作权归作者所有

郑加威
粉丝 145
博文 194
码字总数 402030
作品 0
杭州
架构师
私信 提问
内存优化(使用SparseArray和ArrayMap代替HashMap)

支持原文:http://tryenough.com/java-sparseArray HashMap 关于HashMap的知识请看这篇 优秀文章: SparseArray SparseArray 的使用 支持原文:http://tryenough.com/java-sparseArray 创建 ......

TryEnough
03/12
0
0
Android编程之SparseArray详解

最近编程时,发现一个针对HashMap<Integer, E>的一个提示: 翻译过来就是:用SparseArray<E>来代替会有更好性能。 那我们就来看看源码中SparseArray到底做了哪些事情: 一、构造 从构造方法我...

天下杰论
2013/06/24
0
2
Apache Lucene 2.9.1 发布

Lucene是一套用于全文检索和搜寻的开源程式库, 由Apache软件基金会支持和提供。Lucene提供了一个简单确强大的应用程式接口,能够做全文索引和搜寻,在Java开发环境里Lucene是一个 成熟的免费...

红薯
2009/11/08
2K
0
RichFaces自动构建树实现

树形结构在软件系统中是使用频率非常大的一种数据结构,包括一些算法的实现也是基于树形结构来进行的,比如基于二叉树的二分查找法等等。在软件系统中,树形结构更多的体现在树形菜单的构建上...

菜根乱谭
2009/10/08
250
0
148. Sort List - LeetCode

Solution 148. Sort List Question 题目大意:对链表进行排序 思路:链表转为数组,数组用二分法排序 Java实现:

yysue
2018/07/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

“旧城改造”的背后——银泰新零售阿里云解决方案(上)

相关免费课程《银泰新零售上云解决方案精讲》上线中 立足实战 讲透经典案例 助你快速理解新零售 第一节学习地址 第二节学习地址 传统线下商业体上云的案例 与其说银泰上云,倒不如说银泰“旧...

阿里云官方博客
9分钟前
0
0
记一次升级Oracle驱动引发的死锁

问题描述 近期项目需要从虚拟机环境迁移到容器环境,其中有一个项目在迁移到容器环境之后的两天之内出现了2次“死锁(deadlock)”的问题,部分关键日志如下: Found one Java-level deadlock:...

ksfzhaohui
11分钟前
2
0
MySQL 中的 information_schema 数据库

欢迎查看原文 - 本博客仅记录 https://blog.csdn.net/kikajack/article/details/80065753 -- 是否开启bin_log日志: off为关闭-- show variables like 'log_%'; show variables like '......

莫库什勒
19分钟前
0
0
Random在高并发下的缺陷以及JUC对其的优化

Random可以说是每个开发都知道,而且都用的很6的类,如果你说,你没有用过Random,也不知道Random是什么鬼,那么你也不会来到这个技术类型的社区,也看不到我的博客了。但并不是每个人都知道...

编程SHA
23分钟前
0
0
T5大牛带你解析:如何实现分布式技术

1.分布式事务 2. 分布式锁 Java 原生 API 虽然有并发锁,但并没有提供分布式锁的能力,所以针对分布式场景中的锁需要解决的方案。 分布式锁的解决方案大致有以下几种: 基于数据库实现 基于缓...

李红欧巴
35分钟前
32
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部