二分查找

文章目录

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

相关文章

来自专栏C++

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

1182
来自专栏AILearning

Map集合

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

2086
来自专栏Java帮帮-微信公众号-技术文章全总结

第十六天 常用API-Date&DateFormat&Calender&System&Math&基本类型包装类&正则【悟空教程】

第十六天 常用API-Date&DateFormat&Calender&System&Math&基本类型包装类&简单正则表达式【悟空教程】

832
来自专栏成猿之路

Java面试题-基础篇一

1013
来自专栏vue学习

JS数据结构与算法-链表

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

901
来自专栏个人分享

栈的压入、弹出序列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序...

672
来自专栏电光石火

HashSet集合中hashCode及equals方法详解

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

1729
来自专栏Kevin-ZhangCG

[ Java面试题 ] 集合篇

1827
来自专栏转载gongluck的CSDN博客

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

算数运算符 计算机,顾名思义就是负责进行 数学计算 并且 存储计算结果 的电子设备 目标 算术运算符的基本使用 01. 算数运算符 算数运算符是 运算符的一种 ...

3567
来自专栏曾大稳的博客

c++基础语法

注意:在开发过程中,cpp或者c会被编译为dll或者so供其调用者使用,一般把public的函数定义到h文件,不然调用者都不知道有哪些函数。

943

扫码关注云+社区