JAVA - 二進制搜索 - 鍵值返回索引

我有以下問題需要解決，但是有點困難。如果有人能提供幫助，我會非常感激。JAVA - 二進制搜索 - 鍵值返回索引

總之在歸結爲如下：

如果搜索關鍵字是該陣列中 - 它返回最小的索引i針對其[i]是等於鍵
如果搜索關鍵字不在數組中，但是更大 - 它返回最小索引i作爲-i，其中a [i]大於關鍵字
如果搜索關鍵字不在數組中但更小 - 則返回-j其中j是陣列中最後一個元素的索引

我有搜索關鍵字的代碼，但我不知道上述如何返回指數...

import java.util.Arrays; 
public class BinarySearchIndex2 { 

    // a working recursive version 
    public static int search(String key, String[] a) { 
     return search(key, a, 0, a.length); 
    } 

    public static int search(String key, String[] a, int lo, int hi) { 
     // possible key indices in [lo, hi) 
     if (hi <= lo) return -1; 

     int mid = lo + (hi - lo)/2; 
     int cmp = a[mid].compareTo(key); 
     if  (cmp > 0) return search(key, a, lo, mid); 
     else if (cmp < 0) return search(key, a, mid+1, hi); 
     else    return mid; 
    } 

    public static void main(String[] args) { 

     String key = args[0]; 
     int sizeoflist = StdIn.readInt(); 
     String[] a = new String[sizeoflist]; 
      int counter = 0; //counter for while loop to fill array a 

     while (!StdIn.isEmpty()){ 

      a[counter] = StdIn.readString(); 
      counter++; 

     } 

     Arrays.sort(a); // sort the words (if needed) 

     if (search(key, a) < 0) ; /* System.out.println();*/ 
     else if (search(key, a) > 0) ; 
     else if (search(key, a) = 0) ; 

    } 
}

會很高興，如果有人能幫助我與這件事.. 。

謝謝！

來源

2011-04-25 ISJ

b.t.w - 這是一項家庭作業嗎？（如果是這樣，請相應標記） – RonK 2011-04-25 20:05:36

String.compareTo執行字典對比。這意味着它可以決定「50」>「100」，而顯然50是您所期望的。這將影響您的Arrays.sort調用，因此您的陣列已經混亂。

是否必須要有public static int search(String key, String[] a)作爲您的API？

如果您可以將其更改爲public static int search(int key, int[] a)它將使您的API工作（假設您沒有任何錯誤，我錯過了）。

希望這是你所指的。

編輯：一些很好的調整到問題分析。

來源

2011-04-25 19:56:27 RonK

@RonK你好，是的，我試過那個，但是我不確定compareTo的Int相當於什麼......是否有可能讓我看到正確的方向？謝謝！ – ISJ 2011-04-25 19:58:41

@ISJ：'int'的'compareTo'等價於...普通'<', '> ='等 – ColinD 2011-04-25 20:01:18

@ISJ - 如果使用int而不是String，它應該對你的基本假設API是正確的（數組已排序並且比較正確）。 – RonK 2011-04-25 20:03:11

重要的一點是在這裏：

if (hi <= lo) return -1;

這時候你有一個子陣列搜索大小爲0，這意味着該元素是不是有發生。現在想想：規範對這裏的返回值有什麼看法？

來源

2011-04-25 19:52:51

@Ebermann好吧，如果不存在，它應該測試大於或小於，然後返回相應的索引？ – ISJ 2011-04-25 19:55:29

你的結果條件有點奇怪，但我認爲'return -hi'，'return' -hi-1'和'return -hi + 1'是你想要的。（在紙上做一些測試，並清楚你在這裏需要什麼。）可能有一個'hi == a.length'的特殊情況。 – 2011-04-25 20:29:23

JAVA - 二進制搜索 - 鍵值返回索引

回答

相關問題