java與二進制搜索重複，返回所有匹配

（使用java）我有一個地址簿創建，並可以從中選擇一個菜單，在地址簿中做不同的事情。選擇菜單項2，您可以在書籍中查找姓氏是想要搜索的任何成員（從控制檯輸入）。我在地址簿中查找該書中包含的姓氏。我搜索的一些名稱有很多。當我進行二進制搜索（強制使用二進制）時，我只返回其中一個名稱，而不是返回與我的搜索名稱匹配的所有名稱。這裏是我的代碼：java與二進制搜索重複，返回所有匹配

case '2': //search by last name// only returning 1 person.... 

     name.lastName=""; 
     System.out.println("Please enter the last name of the person you 
          are looking for."); 
     name.lastName = console.next(); 

     int find = binarySearchLast(name); 
     System.out.println(find); 
     System.out.println(bookMembers[find]); 
     process(); 
     break; 


private int binarySearchLast(ExtPerson name) 
{ 
    int first = 0; 
    int last = nMembers; //number of people in the book 
    int mid = 0; 

    boolean found = false; 

    while (first <= last && !found) 
    { 
     mid = (first + last)/2; 
     //System.out.println("This is the mid : "+mid); 
     if (bookMembers[mid].lastName.compareTo(name.lastName)==0) 
      found = true; 
     else if (bookMembers[mid].lastName.compareTo(name.lastName)<0) 
      first = mid + 1; 

     else 
      last = mid - 1; 
     //System.out.println("This is the mid : "+mid); 
    } 

    if (!found) 
     mid = -1; //it is an unsuccessful search 
    // System.out.println("This is the mid : "+mid); 
    return mid; 
}//end binarySearch

該代碼有效，但只返回具有該姓氏的人之一。實際上（取決於所搜索的姓名）多達三個可匹配搜索名稱的人。我想要所有的比賽回來。感謝您的任何幫助

來源

2013-11-26 user2314533

只需搜索列表中沒有找到條件。你找到的條件是什麼阻止循環，只給你第一個找到的項目。

while (first <= last) 
{ 
    mid = (first + last)/2; 
    //System.out.println("This is the mid : "+mid); 
    if (bookMembers[mid].lastName.compareTo(name.lastName)==0) 
     // do something, maybe add to a ist of found names or just print 
    else if (bookMembers[mid].lastName.compareTo(name.lastName)<0) 
     first = mid + 1; 

    else 
     last = mid - 1; 
    //System.out.println("This is the mid : "+mid); 
}

來源

2013-11-26 00:42:47

當我這樣做時，我試着像你說的那樣只是打印出這個名字，但它卻陷入了一個無限循環中，只是打印出第一個找到名字的時間。 – user2314533

首先，我打算寫，非常感謝！我也不應該把usd大寫字母鎖定在那裏...來想想看，我聽說這暗示着大喊大叫。我的歉意 – user2314533

所以你目前陷入無限循環？ –

只能從一個方法返回一個int值，因此，在某些時候你必須做額外的工作....擴大搜索....

二進制搜索不一定會找到第一個或最後一個或任何其他特定的結果......所以，你必須做的第一件事是 - 轉移到一個'好'的位置，這是有意義的'第一'匹配：

if (!found) 
    mid = -1; //it is an unsuccessful search 
// System.out.println("This is the mid : "+mid); 
while (mid > 0 && bookMembers[mid].lastName.equals(bookMembers[mid-1].lastName)) { 
    mid--; 
} 
return mid;

然後，在您的調用代碼中，您可以做相反的事情：

int findfrom = binarySearchLast(name); 
    int findto = findfrom + 1; 
    while (findto < bookMembers.length && bookMembers[findfrom].lastName.equals(bookMembers[findto].lastName)) { 
     findto++; 
    } 
    // the values findfrom (inclusive) to findto (exclusive) match.

來源

2013-11-26 00:46:16 rolfl

java與二進制搜索重複，返回所有匹配

回答

相關問題