欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java二分查找法

程序员文章站 2024-03-16 09:10:10
...

基本思路:

1、提示用户输入数字,接受该数字。

2、利用随机数生成一组数。

3、冒泡排序。(因为二分法只适用于有序数列)

4、利用二分法查找该数

   (1)、计算出数组的中间位置,具体方法是开始位置的索引加上结束位置的索引除以二;

   (2)、取出中间位置的值和要查找的数字比较,根据比较结果决定,根据查找结果决定下一查找的部分;

           1)、如果中间位置的值等于要查找的数字-----输出结果

           2)、如果中间位置的值大于要查找的数字-----结束索引-1

           3)、如果中间位置的值小于要查找的数字-----开始索引+1

           4)、循环一直到开始索引大于结束索引相同为止

   (3)、下一查找部分中间位置同样用开始位置的索引加上结束位置的索引除以二;

 

   //用户输入数字
                System.out.println("请输入要查询的数字");
		Scanner sc=new Scanner(System.in);
		int chazhao=sc.nextInt();
		
		//前提条件:有序数组 
		
		//1、生成随机数组
		Random a=new Random();
		int[] ary=new int[10];
		for(int i=0;i<ary.length;i++)
		{
			ary[i]=a.nextInt(100);
		}
		
		//2、冒泡排序
		
		for(int i=0;i<ary.length-1;i++)
		{
			for(int j=0;j<ary.length-1;j++)
			{
				if(ary[j]>ary[j+1])
				{
				  int t = ary[j];
				  ary[j]=ary[j+1];
				  ary[j+1]=t;
				}
			}
		}
	    for(int k:ary)
	    {
	    	System.out.print(k+"  ");
	    }
		
		//3、二分查找
            int jishu=0;    //定义计数器
	    int start=0;   //开始位置的索引
	    int end=ary.length;    //结束位置的索引
	    int zhong=0;  //定义一个变量作为中间位置的索引
	    while(true)
	    {
	    	zhong=(start+end)/2;    //中间位置索引等于开始位置索引加结束位置索引除以二
	    	jishu++;      //计数器加一
	    	if(ary[zhong]==chazhao)
	    	{
	    		System.out.println("找到了,共查找了"+jishu+"次");
	    		break;
	    	}
	    	else if(ary[zhong]>chazhao)
	    	{	    		
	    		end=zhong-1;
	    	}
	    	else
	    	{	    		
	    		start=zhong+1;
	    	}
	    	if(start>end)
	    	{
	    		System.out.println("没有找到该数");
	    		break;
	    	}
	    }

  

 

 

运行结果:

 

Java二分查找法Java二分查找法