[Java]搜尋演算法-循序搜尋法、二元搜尋法

之前提供過C#版本的搜尋演算法循序搜尋法(Linear/Sequential-Search)二元搜尋法(Binary-Search),現在這是由Java撰寫而成的,整體來講是一樣的。

循序搜尋法

就是直接用迴圈一個個去比對,找到時就跳出。

二元搜尋法

需要先把要搜尋的數列先排序,由小到大,規則是先取前後二索引數,相加除二,也就是取中間數當索引值,然後跟要搜尋的數字做比較,如果一樣就是找到了,如果中間的數比要搜尋的數大,代表要搜尋的數在左邊數列,右邊數列則放棄,相反之,如果中間數比要搜尋的數小,代表要搜尋的數在右邊數列,左邊數列則放棄

執行結果如下:

結果的第一次的搜尋是循序搜尋,第二次是二元搜尋

javaSearch演算法1.png

第二個範例

javaSearch演算法2.png




原始碼如下:

package test;
import java.util.Scanner;
public class SearchTest {
//循序搜尋
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;//找不到時
}
public static void main(String args[])
{
//輸入物件
Scanner in = new Scanner(System.in);
//循序搜尋範例
int[] list = {2,4,5,1,3,4,5,6,7,8};
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);
}
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("找不到資料!");
}
}

One thought to “[Java]搜尋演算法-循序搜尋法、二元搜尋法”

發表迴響