关于二分法查找Java的实现
对于一维数组的查找我们采用一个for循环遍历一次数组就可以实现,但有时候当数组太大,用二分法来实现
可以节省更多的内存,当然二分法也只能实现有序序列的查找,这里我们就以一个递增的数组来说
输入一个人数组,关于二分法的实现主要的就是设定一个中间值mid = (low + high)/2
假设我们要查找的数为 m
- 当mid=m急速表示我们找到了这个数,返回该数的位置;
- 当mid<m时,因为数组时递增的,就表示我们所查找的数在mid的右边,我们就让low = mid+1;
- 当mid>m时,因为数组时递增的,就表示我们所查找的数在mid的左边,我们就让right = mid-1;
- 如果一直找不到就表示不存在,返回-1了。
具体的Java代码如下:
package com.dxh;
import java.util.Scanner;
public class DichotomySearch {
static int num;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("按要求输入:");
int high = in.nextInt()+1;//输入数组的长度
int low = in.nextInt();//输入开始查询的位置
int findvalue = in.nextInt();//输入要查找的值
int [] array = new int [high];//输入要查询的数组
for(int i = 0;i<high;i++){
array[i] = in.nextInt();
}
System.out.println("查询的数的位置在"+SearchResult(array, low, high-1, findvalue));
System.out.println("查询轮数"+num);
num = 0;
System.out.println("查询的数的位置在"+SrearchResult1(array, findvalue));
System.out.println("查询轮数"+num);
}
/*
递归实现二分查找
需要知道开始和结束的位置
*/
public static int SearchResult(int [] array,int low ,int high,int findValue){
if(array == null)return -1;
num++;
if(low<=high){
int mid = (low + high)/2;
if(array[mid] == findValue){
return mid;
}else if(array[mid] < findValue){
return SearchResult( array, mid+1, high, findValue);
}else{
return SearchResult(array, low, mid-1, findValue);
}
}else{
return -1;
}
}
/**
* 循环来实现二分查找
*/
public static int SrearchResult1(int [] array,int findvalue){
if(array == null) {
return -1;
}
int high = array.length-1;
int low = 0;
while(low<=high){
num++;
int mid = (low+high)/2;
if(array[mid] == findvalue){
return mid;
}else if(array[mid]<findvalue){
low = mid+1;
}else{
high = mid-1;
}
}
return -1;
}
}
-
这是结果图
程序结果图
网友评论