Java二分查找（OJ）

Problem B: 二分查找

Time Limit: 1 Sec Memory Limit: 128 MB Description

计算在一个有序序列中查找关键字的次数（二分查找）

Input

输入数据有多组，每组数据包括三个整数n、m(n<=m)和k。

Output

输出在n到m范围内，二分查找k的次数。

Sample Input Copy

10 20 1

Sample Output Copy

3

Java代码：

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int k=sc.nextInt(); int count=0; while(n<m){ count++; int b=(m+n)/2; if(k<b) m=b-1; else if(k>b) n=b+1; else break; } System.out.println(count); } }

运行结果：

Language: Java Result: Accepted Time:116 ms Memory:10236 kb

或者这样：

import java.util.*; public class Main { public static void main(String[]args) { Scanner sc=new Scanner(System.in); int []a=new int [2]; a[0]=sc.nextInt(); a[1]=sc.nextInt(); int k=sc.nextInt();//被查找的数 int count=0; while(a[0]<a[1]) { count++; int b=(a[0]+a[1])/2; if(k<b) a[1]=b-1; else if (k>b) a[0]=b+1; else break; } System.out.println(count); } }

运行结果也是对的（代码稍微改了一下🤦‍🤦‍🤦‍）

C语言代码：

拓展：

从输入的数组中查找要找的那个数字，如果存在的话，说明找到了，输出“YES”，并且输出查找了几次；如果没找到，输出“NO”。

//代码以后补🤦‍🤦‍🤦‍ //运行有错误，放在Eclipse里怕以后找不到,所以就先放到这里了 public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt();//看人家叫你从几个数中查找🤦‍🤦‍ 数组长度 int[] bs =new int [n]; for(int i=0;i<bs.length;i++) { bs[i]=sc.nextInt();//读入数组 } for(int i=0;i<n-1;i++) { for(int j=0;j<n-i-1;j++) { if(bs[j]>bs[j+1]) { int temp=bs[j]; bs[j]=bs[j+1]; bs[j+1]=temp; } //冒泡排序！！进行二分查找必须先排序！！ } } int low=0,mid; int high=bs.length-1; int m=sc.nextInt(); //需要找的数 int count=0; //比较的次数 while(low<=high) { mid=(low+high)/2; if(m<bs[mid]) { high=mid-1; //high=mid-1 count++; } else if (m>bs[mid]) { low= mid+1; //low= mid+1 count++; } else { count++; System.out.println("找到了,下标是" + mid + "比较了" + count); break; } } if(low>high) { System.out.println("未找到"+"比较了" + count); } } }

运行结果：

END