排序數組的二進制搜索

Question

我正在嘗試使用此二進制搜索代碼搜索降序排序數組。但是，在對它進行排序並嘗試搜索後，它不會返回任何結果，只是一個永遠不會消失的加載圖標，就好像它具有無限循環一樣。我不確定問題是什麼，因爲代碼看起來合乎邏輯。

這是aspx 4.0 framework，c＃。提前致謝！

protected void Button2_Click(object sender, EventArgs e) 
    { 
     String item = TextBox1.Text; 
     int target = Convert.ToInt16(item); 
     int mid, first = 0, last = mynumbers.Length - 1; 

     //for a sorted array with descending values 
     while (first<=last) 
     { 
      mid = (first + last)/2; 
      if (target < mynumbers[mid]) 
       first = mid + 1; 
      if (target > mynumbers[mid]) 
       last = mid - 1; 
      else 
       Label11.Text = "Target " + item + " was found at index " + mynumbers[mid]; 

     } 

Answer 1

有一個在Array類二進制搜索：

public class ReverseComparer<T> : IComparer<T> 
    { 
     public int Compare(T x, T y) 
     { 
      return Comparer<T>.Default.Compare(y, x); 
     } 
    } 

：

int index = Array.BinarySearch(mynumbers, target); 

降序排序，這可以很容易地用ReverseComparer這是很容易寫這樣完成然後：

int index = Array.BinarySearch(numbers, 7, new ReverseComparer<int>()); 

如果這是一項學術性練習，並且您必須使用自定義搜索，當然這不適用。如果它有成爲一個類的自定義算法，那麼問題是，當發現你必須打破循環的，並且該指數處於mid，而不是在mynumbers[mid]：

//for a sorted array with descending values 
    while (first<=last) 
    { 
     mid = (first + last)/2; 

     if (target < mynumbers[mid]) 
     { 
      first = mid + 1; 
     } 

     if (target > mynumbers[mid]) 
     { 
      last = mid - 1; 
     } 

     else 
     { 
      // the index is mid, not mynumbers[mid], and you need to break here 
      // once found or it's an infinite loop once it finds it. 
      Label11.Text = "Target " + item + " was found at index " + mid; 
      break; 
     } 
    } 

而實際上，我ð可能設置一個布爾標誌，而不是保持算法純的，沒有混合與輸出顧慮發現，這也將使其更容易知道發生了什麼事，如果你退出循環使用未發現：

bool found = false; 

    //for a sorted array with descending values 
    while (!found && first<=last) 
    { 
     mid = (first + last)/2; 

     if (target < mynumbers[mid]) 
     { 
      first = mid + 1; 
     } 

     if (target > mynumbers[mid]) 
     { 
      last = mid - 1; 
     } 

     else 
     { 
      // You need to stop here once found or it's an infinite loop once it finds it. 
      found = true; 
     } 
    } 

    Label11.Text = found 
     ? "Item " + item + " was found at position " + mid 
     : "Item " + item + " was not found"; 

Answer 2

中彈黑暗：

if (target < mynumbers[mid]) 
    first = mid + 1; 
else if (target > mynumbers[mid]) 
    last = mid - 1; 
else 
{ 
    .... 
    break; 
} 

我懷疑你來回彈跳中旬+ 1和中1

Answer 3

之間這是一個正確的：

如果target< mynumbers[mid]，那麼你還有最後採取中期1， 因爲我們在較低的範圍內，即首先進行搜索以中期1

while (first<=last) 
     { 
      mid = (first + last)/2; 
      if (target == mynumbers[mid]) 
      Label11.Text = "Target " + item + " was found at index " + mynumbers[mid]; 

      else if (target < mynumbers[mid]) 
       last = mid - 1; 
      else (target > mynumbers[mid]) 
       first = mid + 1; 

      } 

Answer 4

//this works fine with these Test cases  
// has to check if (target == mynumbers[mid])  
// this is for an array with ascending order. 
class Program 
{ 

    static void Main(string[] args) 
    { 
     // TEST cases: 
     // for 8: item 8 was not found 
     // for 4: item 4 found at Position 3 
     // for 1: item 1 found at position 0 
     // for 0: item 0 was not found 


     int target =8; 
     int searchkey = target; 

     int[] mynumbers = { 1, 2, 3, 4, 5 }; 

     int mid=0, first = 0, last = mynumbers.Length - 1; 

     bool found = false; 

     //for a sorted array with ascending values 
     while (!found && first <= last) 
     { 
      mid = (first + last)/2; 

      if (target == mynumbers[mid]) 
       found = true; 
      else 
      { 

       if (target > mynumbers[mid]) 
       { 
        first = mid + 1; 
       } 

       if (target < mynumbers[mid]) 
       { 
        last = mid - 1; 
       } 

      } 

     } 

     String foundmsg = found 
      ? "Item " + searchkey + " was found at position " + mid 
      : "Item " + searchkey + " was not found"; 
     Console.WriteLine(foundmsg); 
    } 
} 

Answer 5

其工作˚F或者我

public static int search(int[] arr, int value) 
{ 
    Debug.Assert(arr.Length>0); 
    var left = 0; 
    var right = arr.Length - 1; 

    while (((right - left)/2) > 0) 
    { 
     var middle = left + (right - left)/2; 
     if (arr[middle] < value) 
      left = middle + 1; 
     else 
      right = middle; 
    } 
    return arr[left] >= value ? left : right; 
}