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

回答

相关问题