二分查找

文章目录

  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 条评论
登录 后参与评论

相关文章

来自专栏电光石火

HashSet集合中hashCode及equals方法详解

首先我们熟知HashSet集合中元素存储的特点: 1)不允许元素重复; 2)不会记录元素添加的先后顺序; 3)HashSet中比较两个对象是否相同...

1859
来自专栏AILearning

Map集合

Collection |--List:元素是有序的,元素可以重复,因为该集合体系有索引 |--ArrayList:底层的数据结构使用的是数据结构。特点:查询...

2406
来自专栏小怪聊职场

Java|Map、List与Set的区别

47912
来自专栏用户3030674的专栏

约瑟夫环(排成圈)

/** * 约瑟夫环问题主要是考虑下标问题,只要解决了下标控制问题,这个题目就不难了 * 在这里我是分成了3中情况: * 1,下标小于剩余人数时:删...

942
来自专栏Kevin-ZhangCG

[ Java面试题 ] 集合篇

2067
来自专栏赵俊的Java专栏

二分查找

1201
来自专栏向治洪

java 之容器

在Java中,我们想要保存对象可以使用很多种手段。我们之前了解过的数组就是其中之一。但是数组具有固定的尺寸,而通常来说,程序总是在运行时根据条件来创建对象,我们...

2608
来自专栏vue学习

JS数据结构与算法-链表

一个链表的结构 现实中的举例说明就是火车。每节车厢是链表的元素,车厢间的连接就是指针:

1241
来自专栏hbbliyong

Python正则进阶

  返回一个列表,如果正则表达式中没有分组,则列表中包含的是所有匹配的内容,如果正则表达式中有分组,则列表中的每个元素是一个元组,元组中包含子分组中匹配到的内容...

1353
来自专栏C++

python笔记:#005#算数运算符

1632

扫码关注云+社区

领取腾讯云代金券