Java - 遞歸二進制搜索通過Arraylist

所以我需要一種方法的幫助。使用遞歸二分搜索算法來搜索數組列表。Java - 遞歸二進制搜索通過Arraylist

private static < E extends Employee > int binarySearch(ArrayList<E> list, int firstElem, int lastElem, String searchLastName) 
{  
    int middle=0; 

    if(firstElem > lastElem){ 
     return -1; 
    } 

    middle = (firstElem + lastElem)/2; 

    if(list.get(middle).getLastName().equals(searchLastName)){ 
     return middle; 
    }else if(   ){ // <-------------? 
     return binarySearch(list,middle+1,lastElem, searchLastName); 
    } 
    else { 
     return binarySearch(list, firstElem, middle -1, searchLastName);    
    } 
}

這是我到目前爲止，但我堅持的邏輯部分。任何幫助，將不勝感激。

來源

2014-11-23 Rib

既然你說你被困在邏輯部分，我認爲一個僞代碼的答案就足夠了。

首先，我假設你的數組按升序排序。如果數組未被排序，則二進制搜索是不可能的。由於它是排序的，所以每次比較都可以將問題的大小減半。所以如果答案是在數組的右邊，那麼你就丟掉左邊的部分，只把它遞歸到右邊的部分。

因爲每次遞歸調用的時候問題都會變小一半，你會得到O（log n）的運行時間。

的基本邏輯是這樣的：

binarySearch(list,begin,end,query) 
    if (begin > end) 
     return -1 
    middle = (begin + end)/2 
    if list[middle].value == query 
     return middle 
    if list[middle].value < query 
     return binarySearch(list,begin,middle,query) 
    return binarySearch(list,middle,end,query)

來源

2014-11-23 21:58:23 wvdz

給你

你要實現一個比較的方法來決定你就會在搜索其中一半

我做了一個簡單的。方法來比較兩個字符串..它轉換爲一個數字值。

入住此示例代碼：

import java.util.ArrayList; 

public class BinarySearch { 

    public static void main(String[] args) { 
     ArrayList<Employee> arrayList = new ArrayList<Employee>(); 
     for (int i = 0; i < 10; i++) { 
      Employee employee = new Employee(); 
      employee.setLastName("name" + i); 
      arrayList.add(employee); 
     } 
     System.out.println(arrayList); 
     System.out 
       .println(binarySearch(arrayList, 0, arrayList.size(), "name6")); 

    } 

    private static <E extends Employee> int binarySearch(ArrayList<E> list, 
      int firstElem, int lastElem, String searchLastName) { 
     int middle = 0; 

     if (firstElem > lastElem) { 
      return -1; 
     } 

     middle = (firstElem + lastElem)/2; 

     if (list.get(middle).getLastName().equals(searchLastName)) { 
      return middle; 
     } else if (compare(searchLastName, list.get(middle).getLastName()) >= 0) { // <-------------? 
      return binarySearch(list, middle + 1, lastElem, searchLastName); 
     } else { 
      return binarySearch(list, firstElem, middle, searchLastName); 
     } 
    } 

    /** 
    * Compare to strings. 
    * @param str1 
    * @param str2 
    * @return 
    */ 
    public static int compare(String str1, String str2) { 
     int minLength = Math.min(str1.length(), str2.length()); 
     if (getValue(str1, minLength) > getValue(str2, minLength)) { 
      return 1; 
     } else { 
      return -1; 
     } 
    } 

    /** 
    * Calculate a value to a string to compare it. 
    * @param str 
    * @param length 
    * @return 
    */ 
    public static int getValue(String str, int length) { 

     int result = 0; 

     for (int i = 0; i < length; i++) { 
      char c = str.charAt(i); 
      result += Math.pow(10, i) * c; 
     } 

     return result; 
    } 

}

下面是一個示例輸出：

[name0, name1, name2, name3, name4, name5, name6, name7, name8, name9] 
6

我希望這可以幫助。

來源

2014-11-23 22:34:20

Java - 遞歸二進制搜索通過Arraylist

回答

相關問題