Binary search for sorted array

Question

I am trying to find an array sorted in descending order using this binary search code. However, after I sorted it and try to search, it does not return with any result, it’s just a loading icon that never disappears, as if it has an infinite loop. I am not sure what the problem is because the code looks logical.

This is aspx with 4.0 framework, C #. Thanks in advance!

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

The Array class has a binary search:

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

In descending order, this can easily be done with ReverseComparer , which is easy to write like this:

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

Then:

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

If this is an academic exercise, and you should use a custom search, of course, this will not apply. If this is a special algorithm for the class, then the problems are that you have to exit the loop when it is detected, and the index is in mid , not in 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 an infinite loop once it finds it. Label11.Text = "Target " + item + " was found at index " + mid; break; } } 

And in fact, I would most likely set the bool flag to keep the algorithm clean and not mix find with output problems, this will also make it easier to talk about what happened if you exit the loop if not found:

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

Shot in the dark:

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

I suspect you are bouncing back and forth between mid + 1 and mid-1.

Answer 3

This one is correct:

if target< mynumbers[mid] , then you need to take the latter in mid-1, because we have to search in the lower range, that is, first to mid 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

Worked for me

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