我需要幫助解決這個算法

-2

使用類似二進制搜索算法來找到地方算法，其中產品是：一）插入排序列表我需要幫助解決這個算法

if (the item is already in this list) 
    // output an appropriate message 
else 
    // use the method insertAt to insert the item in the list

我寫的方法，它不工作

public int search(int item) 
{ 
    int first=0; 
    int last=length-1; 
    int mid=-1; 
    boolean found =false; 
    while(first<=last && !found){ 
     mid=(first+last)/2; 
     if(list[mid]==item) 
      found=true; 
     else 
      if(list[mid]-item>0) 
       last=mid-1; 
      else 
       first=mid+1; 

    } 
    if(found) 
     return mid; 
    else 
     return -1; 

} 

public void insert(int item) { 
    int loc = search(item); 

    if (loc != -1 && list[loc] != item) 
    insertAt(loc, item); 
    else 
    System.out.println("the item is already existing"); 
}

來源

2012-12-17 Jamal Kushha

任何你沒有使用像HashSet這樣的現有Set實現的原因？ – Thomas

不工作如何？我們可以看到你的搜索（）方法嗎？ –

@Thomas推測原因是「學校派遣」並不是一個延伸。 – millimoose

我懷疑你希望你的測試條件是loc == -1 || list[loc] != item這些都是其中（a）您找不到項目或（b）在發現該項目不匹配的條件。條件（b）似乎不應該發生，因爲你只是搜索它，但你比我更瞭解你的代碼。

您可能想要做的一件事是修改您的搜索，以便在找不到項目時返回該項目應該插入的位置的倒數而不是-1。然後，你可以這樣做：

if (loc < 0) { 
    insertAt(-loc,item); 
    }

來源

2012-12-17 15:29:05 tvanfosson

試試這個

int[] a = { 1, 2, 3, 5, 6 }; 
int key = 4; 
int p = Arrays.binarySearch(a, key); 
if (p >= 0) { 
    System.out.println("the item is already exiset"); 
} else { 
    p = -p - 1; 
    a = Arrays.copyOf(a, a.length + 1); 
    System.arraycopy(a, p, a, p + 1, a.length - 1 - p); 
    a[p] = key; 
    System.out.println(Arrays.toString(a)); 
}

輸出

[1, 2, 3, 4, 5, 6]

來源

2012-12-17 15:35:19

會工作，但我認爲他想要一個劃傷算法。聞起來像學校作業:) – cjds

最好的事情將是編輯二進制搜索本身。使它如此，如果二進制搜索沒有找到flag則在搜索結束時插入flag。

public void insert(int item,int[] list, int min, int max) { 
     if(min>= max){ 
      //insert element at min 
     } 
     int mid=(min+max)/2; 

     if(list[mid]<item){ 
       insert(item, list, mid+1, max) 
     } 
     if(list[mid]>item){ 
       insert(item, list, min, mid-1) 
     } 
     else{ 
       System.out.println("the item is already existing"); 
     } 

}

來源

2012-12-17 15:37:02 cjds

我需要幫助解決這個算法

回答

相關問題