二分查找

文章目录

  1. 1. 二分查找算法
    1. 1.1. 准备
    2. 1.2. 非递归实现
    3. 1.3. 递归实现

二分查找算法

  • 对一个有序数组的查找

准备

  • 使用冒泡排序算法对数组排序

12345678910111213

//冒泡排序 , 从小到大public void bubbleSort(Integer[] array){ //外层遍历n-1次 for (int i = 0; i < array.length-1; i++) { for(int j=array.length-1;j>i;j--){ if (array[j]<array[j-1]) { Integer t=array[j]; array[j]=array[j-1]; array[j-1]=t; } } }}

非递归实现

  • 传入的数组是一个从小到大的数组

123456789101112131415161718192021222324252627

/** * 二分查找算法 * @param array 数组,必须是从小到大有序的 * @param key 查找的关键字 * @return 如果成功查找到,那么返回索引,否则返回-1 */ public Integer binarySearch(Integer[] array,Integer key){ int low=0; //最前面的索引默认是0 int high=array.length-1; //最后面的索引默认为最后一个 //从小到大的数组,low>high判断数组中是否有元素 if (key<array[low]||key>array[high]||low>high) { return -1; } while(low<=high){ int middle=(low+high)/2; //左右索引的中间值 //如果要查找的数据大于中间值,表示 if (key>array[middle]) { low=middle+1; //那么查找右半部分 }else if (key<array[middle]) { //如果查找的数据小于中间值,那么查找左半部分 high=middle-1; }else { //如果key==middle,那么直接返回middle即可 return middle; } } return -1; //没有找到,返回-1 }

递归实现

12345678910111213141516171819202122

/** * 递归的二分查找 * @param array 从小到大的有序数组 * @param key 需要查找的数 据 * @param low 左边的索引 初始值为0 * @param high 右边的索引 初始值为array.length-1 * @return 查找成功返回索引,否则返回-1 */public Integer recursionBinarySearch(Integer[] array,Integer key,Integer low,Integer high){ //从小到大的数组,low>high判断数组中是否有元素 if (key<array[low]||key>array[high]||low>high) { return -1; } Integer middle=(low+high)/2; //中间索引 if (key>array[middle]) { return recursionBinarySearch(array, key, middle+1, high); }else if(key<array[middle]){ return recursionBinarySearch(array, key, low, middle-1); }else { return middle; }}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏刘望舒

算法(三)初等排序后篇[选择和希尔排序]

1.选择排序 根据上一篇文章讲到的插入排序和冒泡排序,我们把选择排序的数组也分为已排序部分和未排序部分。 图解选择排序 在用图来讲解选择排序之前,我们要先了...

1718
来自专栏LanceToBigData

JavaSE(五)JAVA对象向上转型和向下转型

今天做了一个测试的题目,发现自己还是很多问题没有静下心来做。很多问题是可以自己解决的但是自己一是没有读清题意,二是自己心里太急躁了。所以这个要自己应以为鉴!  ...

1806
来自专栏数据处理

python装饰器

1555
来自专栏互联网杂技

排序算法性能比较

所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

3307
来自专栏ACM算法日常

最长上升子序列(LIS)算法

LIS(Longest Increasing Subsequence)最长上升子序列 一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列...

752
来自专栏静默虚空的博客

排序三 直接插入排序

要点 直接插入排序是一种最简单的插入排序。 插入排序:每一趟将一个待排序的记录,按照其关键字的大小插入到有序队列的合适位置里,知道全部插入完成。 在讲解直接插...

1856
来自专栏liulun

Nim教程【九】

向关注这个系列的朋友们,道一声:久违了! 它并没有被我阉掉,他一定会得善终的,请各位不要灰心 Set集合类型 为了在特殊场景下提高程序的性能设置了Set类型,...

18010
来自专栏老司机的技术博客

人人都能学会的python编程教程2:数据类型和变量

了解一门编程语言最开始就是了解它的数据类型了,python基本的数据类型分为如下几类:

3477
来自专栏Micro_awake web

JavaScript实现八大内部排序算法

? 注:基数排序中:r是关键字的基数,d是长度,n是关键字的个数 1.插入排序 基本思想:在序号i之前的元素(0到i-1)已经排好序,本趟需要找到i对应的元素...

2249
来自专栏编程

宝宝都能学会的python编程教程2:数据类型和变量

数据类型 了解一门编程语言最开始就是了解它的数据类型了,python基本的数据类型分为如下几类: 整数 Python可以处理任意大小的整数,当然包括负整数,在程...

18610

扫码关注云+社区