循序搜索法
就是一个一个去比较,找到时返回;
二元搜索法
二元搜索算法是在排好序的数组中找到特定的元素.
首先, 比较数组中间的元素,如果相同,则返回此元素的指针,表示找到了. 如果不相同, 此函数就会继续搜索其中大小相符的一半,然后继续下去. 如果剩下的数组长度为0,
则表示找不到,那么函数就会结束.
实现代码:
package com.zc.manythread;
import java.util.Random;
import java.util.Scanner;
/**
*
* @author 偶my耶
* 循环查找
* 二元查找
*/
public class LinearSearch {
//循序搜索
public static int LinearSearch(int[] list,int item)
{
for(int i = 0 ; i < list.length;i++)
{
if(list[i]==item)
return i;//找到传回的位置
}
return -1;//找不到时
}
//二元搜寻,传入的数先排序好,由小至大
public static int BinarySearch(int[] list,int item)
{
//初始左右二边
int left = 0 ;
int right = list.length;
//左边的索引位置小于右边的索引的位置
while(left<=right)
{
int mid = (left + right)/2;
if(list[mid]==item)
return mid;
else
{
//所查询值比中间值小,故值会在中间的左边数列
if(list[mid]>item)
{
right = mid -1;
}else
{
left = mid +1;
}
}
}
return -1;//找不到时
}
/**
* 产生随机数组
* @param count
* @return
*/
private static int[] createDate(int count) {
int[] data=new int[count];
Random rand = new Random();
boolean[] bool = new boolean[100];
int num = 0;
for (int i = 0; i < count; i++) {
do {
// 如果产生的数相同继续循环
num = rand.nextInt(100);
} while (bool[num]);
bool[num] = true;
data[i]=num;
}
return data;
}
public static void main(String args[])
{
//输入要查找的数
Scanner in = new Scanner(System.in);
//循序搜寻案列
int[] list = createDate(10);
System.out.println("原始数列:");
for(int i = 0 ; i <list.length ; i ++)
{
System.out.print(list[i]+" ");
}
System.out.println("\r\n请输入要查询的数:");
int searchkey = in.nextInt();
int ans = LinearSearch(list,searchkey);
if(ans>-1)
{
System.out.println("找到数,位置在:"+(ans+1)+"位");
}
else
System.out.println("找不着");
//二元搜寻案列
int[] list2 = {2,4,6,8,10,12,13,14,15,16};
System.out.println("原始数据:");
for(int i = 0 ; i<list2.length ; i ++)
{
System.out.print(list2[i]+" ");
}
System.out.println("\r\n请输入要查询的数:");
int searchkey2 = in.nextInt();
int ans2 = BinarySearch(list2,searchkey2);
if(ans2>-1)
{
System.out.println("找到数,位置在:"+ans2+"位");
}
else
System.out.println("找不着!");
}
}
运行结果
以上就是本文的全部内容了,希望大家能够喜欢。