[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("找不到資料!");
        
        
    
    }
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料