二分查找的核心思想就是根据有序数组的中间值判断目标所在的区间,每比较一次目标所在的范围都会缩小一半,当目标值和中间值相等的时候就找到了该目标值对应的数组下标,查找成功;当low>heigh的时候,就表明没有找到对应的元素,查找失败。
一、递归方式的二分查找
import java.util.Scanner; public class BitSearch{ public static void main(String args[]){ Scanner scanner=new Scanner(System.in); int total=scanner.nextInt(); int[] array=new int[1024]; for(int i=0;i<total;i++){ array[i]=scanner.nextInt(); } int aim=scanner.nextInt(); int resultIndex=bitSearch(array,aim,0,total-1); if(resultIndex==-1){ System.out.println("没有找到目标!"); }else{ System.out.println("查找到的索引值为:"+resultIndex); System.out.println(array[resultIndex]); } } public static void output(int[] array,int total){ for(int i=0;i<total;i++){ System.out.print(array[i]+" "); } System.out.println(); } public static int bitSearch(int[] array,int aim,int start,int end){ if(start<=end){ int mid=(start+end)/2; if(array[mid]==aim){ return mid; } else if(array[mid]>aim){ return bitSearch(array,aim,start,mid-1); }else{ return bitSearch(array,aim,mid+1,end); } } return -1; } }
二、非递归方式的二分查找
只需要替换掉上面的查找方法即可:
public static int bitSearch(int[] array,int aim,int start,int end){ while(start<=end){ int mid=(start+end)/2; if(array[mid]==aim){ return mid; }else if(array[mid]<aim){ start=mid+1; }else{ end=mid-1; } } return -1; }
三、测试方法
使用之前的MyRandom类,但是需要修改一下:
import java.util.Random; public class MyRandom { public static void main(String args[]){ int[] array=new int[1024]; for(int i=0;i<1024;i++){ array[i]=i; } System.out.println("1024"); for(int i=0;i<1024;i++){ System.out.print(array[i]+" "); } System.out.println(); Random random=new Random(); System.out.println(random.nextInt(1024)); // System.out.println(1024); } }
其中
Random random=new Random(); System.out.println(random.nextInt(1024));
用于能够差找到的情况下的测试;
System.out.println(1024);
用于查找不到的情况下的测试(1024不在0-1023之间)
四、测试命令
java MyRandom | java BitSearch
如果找不到:
相关推荐
关于数据结构二分查找程序代码,经典详细。
/* 实验任务: (1) 设计算法创建二叉排序树,按照中序遍历输出数据;查找指定元素,给出结点地址,给出比较次数。 (2) 采用除留余数函数实现散列(哈希)存储,某种方法解决冲突。 */
C语言数据结构,包括栈、队列的操作,二叉树,顺序查找,二分查找,哈夫曼树,图遍历等。
(1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素,并以二分查找的判定树来解释。 (2) 设计出在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法。 (3) 设计算法在...
上课自己写的, C# 数据结构 二分查找
C++数据结构折半查找法二分查找法,算法设计新颖,有利于数据结构初学者的学习!
1.二分查找又称为折半查找,它要求要查找的顺序表必须是有序表,即表中结点按关键字有序.并且要用顺序存储结构。 基本思想是:首先将给定值key与表中中间位置记录的关键字相比较,若二者相等,则查找成功,否则...
一、实验目的: 熟悉各种查找算法及其复杂性,能够根据实际情况选择合适的存储结构。 二、实验要求: 1、掌握查找的基本方法。 2、提交实验报告,报告...编程分别对有序顺序表的顺序查找,二分查找算法进行实现。
数据结构八大算法,详细介绍了算法的如何实现,以及编码过程,有简单到复杂,由浅入深,看看会有很大收获。
二分查找算法,c语言实现,绝对可以运行。快来下载吧
数据结构之查找中的二分查找程序代码~~~~
vc6.0环境下实现c++二分查找,int eFenChaZhao(int *arr,int lo,int k)和int eFenChaZhao(int lo,int *arr,int k) 效果一样。长度在前,数组在后也行,要对应这里的原函数参数数组在作为参数传递给函数时,将自动...
数据结构 查找 源代码 二分查找的算法源码,两种算法的效率比较
简单的初级菜鸟上传的数据结构试验报告,我是大二学的数据结构,主要是帮助那些一点都不会的更菜的菜鸟~!
数据结构查找实验代码 (1) 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素(的下标),并以二分查找的判定树来解释。 第一组测试数据: 数据表为 (1,2,3,4,6,7,8,9,10,11,12,13,17,18,...
1 掌握查找的不同方法,并能用高级... 2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。 3 掌握排序的不同方法,并能用高级语言实现排序算法。 4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。
编程实现有n个元素的有序顺序表上的二分查找算法。查找若成功,输出其位置,还需输出查找次数;若失败,输出提示信息,还需输出比较次数。
C语言数据结构二分查找树,也叫二分排序树的实现代码,
本演示程序用VC6.0编写,完成递归版本和迭代版本的二分查找的实现
合工大数据结构C++二分查找实验报告Visio流程图