解释:二分查找运用在生活的很多方面。例如猜数字游戏,在1到100中选择一个数字,然后进行猜测,用猜测的数字和已知进行比较大小,排除一半一半的可能性,这样最多7步,而采用自然的方法,需要很多次,因而二分查找的时间复杂度更低。
前提:序列有序。
代码实现:
import java.util.*;
import java.util.Scanner;
class BinnarySearch
{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
int []arr = new int[7];
System.out.println("请有序输入一串数字(从小到大)");
for(int i = 0; i < arr.length; i++)
{
arr[i] = input.nextInt();
}
System.out.println("请输入要查询的数字");
int n;
n = input.nextInt();
System.out.println("要查询的数字"+ n + "的位置是:"+Search(arr,n)+1);
}
public static int Search(int[] arr, int n)
{
int right = arr.length - 1;
int left = 0;
while(left <= right)
{
int mid = (right+left) / 2;
if(n == arr[mid]) return mid;
else if(n < arr[mid]) right = mid - 1;
else left = mid + 1;
}
return -1; //表示没有找到
}
}
截图
网友评论