排序数组的二进制搜索

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; 
}