首頁 > 文章 > Java > Java如何實作二進位搜尋？

Java如何實作二進位搜尋？

藏色散人原創: 2019-03-19 13:38:124071瀏覽

在Java中有兩種方法可以進行二進位搜尋。

Java如何實作二進位搜尋？

1.Arrays.binarysearch()適用於也可以是原始資料類型的陣列。

import java.util.Arrays; 
  
public class GFG { 
    public static void main(String[] args) 
    { 
        int arr[] = { 10, 20, 15, 22, 35 }; 
        Arrays.sort(arr); 
  
        int key = 22; 
        int res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 40; 
        res = Arrays.binarySearch(arr, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

輸出：

22 found at index = 3
40 Not found

2.Collections.binarysearch()適用於物件集合，如ArrayList和LinkedList。

import java.util.List; 
import java.util.ArrayList; 
import java.util.Collections; 
   
public class GFG 
{ 
    public static void main(String[] args) 
    { 
        List<Integer> al = new ArrayList<Integer>(); 
        al.add(1); 
        al.add(2); 
        al.add(3); 
        al.add(10); 
        al.add(20); 
   
        int key = 10; 
        int res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = " 
                                                 + res); 
        else
            System.out.println(key + " Not found"); 
  
        key = 15; 
        res = Collections.binarySearch(al, key); 
        if (res >= 0) 
            System.out.println(key + " found at index = "
                                                  + res); 
        else
            System.out.println(key + " Not found"); 
    } 
}

輸出：

10 found at index = 3
15 Not found

如果輸入沒有排序怎麼辦？
如果未對輸入清單進行排序，則結果未定義。

如果有重複怎麼辦？
如果有重複，則無法保證找到哪一個。

Collections.binarySearch如何為LinkedList運作？
此方法在log（n）時間內運行，用於「隨機存取」列表，如ArrayList。如果指定的清單沒有實作RandomAccess介面且很大，則此方法將執行基於迭代器的二進位搜索，該搜尋執行O（n）連結遍歷和O（log n）元素比較。

兩個函數傳回的負值的重要值是多少？
此函數傳回搜尋鍵的索引（如果它包含在陣列中）; 否則，（ - （插入點） - 1）。插入點定義為鍵將插入到陣列中的點：第一個元素的索引大於鍵，或如果陣列中的所有元素都小於指定鍵，則為a.length。請注意，當且僅當找到密鑰時，這可以保證返回值> = 0。

如何在Java中實作我們自己的二進位搜尋？

class BinarySearch 
{ 
    int binarySearch(int arr[], int l, int r, int x) 
    { 
        if (r>=l) 
        { 
            int mid = l + (r - l)/2; 
            if (arr[mid] == x) 
               return mid; 

            if (arr[mid] > x) 
               return binarySearch(arr, l, mid-1, x); 
 
            return binarySearch(arr, mid+1, r, x); 
        } 

        return -1; 
    } 
 
    public static void main(String args[]) 
    { 
        BinarySearch ob = new BinarySearch(); 
        int arr[] = {2,3,4,10,40}; 
        int n = arr.length; 
        int x = 10; 
        int result = ob.binarySearch(arr,0,n-1,x); 
        if (result == -1) 
            System.out.println("Element not present"); 
        else
            System.out.println("Element found at index " +  
                                                 result); 
    } 
}

輸出：

Element found at index 3

Java如何實作二進位搜尋？

相關文章