之前提供過C#版本的搜尋演算法循序搜尋法(Linear/Sequential-Search)及二元搜尋法(Binary-Search),現在這是由Java撰寫而成的,整體來講是一樣的。
循序搜尋法
就是直接用迴圈一個個去比對,找到時就跳出。
二元搜尋法
需要先把要搜尋的數列先排序,由小到大,規則是先取前後二索引數,相加除二,也就是取中間數當索引值,然後跟要搜尋的數字做比較,如果一樣就是找到了,如果中間的數比要搜尋的數大,代表要搜尋的數在左邊數列,右邊數列則放棄,相反之,如果中間數比要搜尋的數小,代表要搜尋的數在右邊數列,左邊數列則放棄
執行結果如下:
結果的第一次的搜尋是循序搜尋,第二次是二元搜尋
第二個範例
原始碼如下:
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("找不到資料!"); } }
不好意思,我想詢問這個程式的Big-O如何運算?