Binary search of a sorted array

Question

I am trying to search a descending sorted array using this binary search code. However, after I sort it, and try to search, it doesn't come back with any result, just a loading icon that never goes away as if it has an infinite loop. I'm 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];

        }

Terpineol

I think... it should be first < last only not <= – Dimitrovo

I tried that too. What happens then is the same thing or it does something weird and gives me the result for the last number only. – Terpineol

Actually <= is correct, you need to go through the loop on an == condition because they could have converged on the same position in the last pass and you need to see if the item is equal to the target. – Folberth

This brings back all kinds of memories when I used to teach algorithms & data structures in C++ at night classes here in St. Louis... – Folberth

Answer 1

There is a binary search in the Array class:

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

For descending order, this can be easily accomplished with a ReverseComparer which is easy to write like:

    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 must use a custom search, of course, this won't apply. If it's got to be a custom algorithm for a class, then the problems are that you must break out of the loop when found, and the index is at mid, not at 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;
        }
    }

And actually, I'd probably set a bool flag instead to keep the algorithm pure and not mix the find with the output concerns, this will also make it easier to tell what happened if you exit the loop with 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'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";

Folberth

Thanks for the response, yeah it has to be a custom search – Terpineol

The OP's array is sorted in descending order. I presume that's why they're doing it themselves. (Also, you don't need to explicitly call the generic overload: the type-inferencing algorithm will automatically choose the most appropriate method -- ie, strongest typed overload.) – Suppurate

@LukeH: Yep, I added the descending twist. If the OP needs custom because of descending, he just needs a ReverseComparer<T> which is a good toolbox item anyway. If it's an academic exercise, however, he does need custom code. – Folberth

@Emmanuel: Do you need custom because it's an academic exercise, or because of descending order? If because of descending order the ReverseComparer<T> - which is a good toolbox class to keep around - will solve it. – Folberth

I need it because it's an academic exercise. Yes this helps A LOT, I couldn't figure out why it kept loading after it found the number. Interesting thing is my teacher from Java 2 had us use this code that I used to do a binary search in there so I just decided to copy it over for this class. Didn't think it would behave differently. – Terpineol

@Emmanuel: Very odd, perhaps the method it is encased in is different or the test data? The same flaws should show in the Java as well. – Folberth

@JamesMichaelHare, and can i use BinarySearch(custom) if i have multiply keys? For example, i have 3 same keys, make binary search and it returns index=2; So,can i suppose that index==1 and\or index==3 contains the same key? – Uniformed

I'm doing a similar assignment and am wondering if there is any reason to not use "else" before the target > mynumbers[mid] comparison? I'm not sure if it's more efficient or a wasteful check. – Bannasch

There is recommendation that middle point should be calculated as mid = lo + (hi - lo) / 2, because implementation above might fail for big arrays. This bug was found in Java implementation of the binary search (research.googleblog.com/2006/06/…). This issue was also mentioned by Eric Lippert https://mcmap.net/q/904717/-generic-binary-search-in-c – Stroganoff

Wouldn't it be faster to guess where our index is instead of always middle the remaining array? Say if the lowest hashcode is -100000 and the highest +100000 and the hashcode of the element I'm looking up is 50000, to "mid" at 75% instead of at 50%? (And then again, and again like this)? – Friederike

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're bouncing back and forth between mid+1 and mid-1

Dipsomaniac

Answer 3

This is one correct :

if target< mynumbers[mid] then you have to take last to mid-1, because we have to search in lower range i.e. 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;

            }

Incestuous

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

Neumeyer

Answer 5

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

Cere

Answer 6

Binary search using C# 12 in .NET 8.

public static class BinarySearcher
{
    public static int FindIndex(int[] sortedData, int item)
    {
        // leftIndex and rightIndex keep track of which part of the array you’ll search in.
        var leftIndex = 0;
        var rightIndex = sortedData.Length - 1;

        // While you haven’t narrowed it down to one element
        while (leftIndex <= rightIndex)
        {
            // Check the middle element
            var midIndex = (leftIndex + rightIndex) / 2;
            var guess = sortedData[midIndex];
            
            if (guess == item) return midIndex;

            // The guess was too high
            if (guess > item)
            {
                rightIndex = midIndex - 1;
            }
            // The guess was too low
            else
            {
                leftIndex = midIndex + 1;
            }
        }
        
        return -1; // The item does not exist.
    }
}

Tested using NUnit 3.

using NUnit.Framework;

public class BinarySearcherTests
{
    [Test]
    public void BinarySearcher_Finds_Item()
    {
        // Arrange
        int[] myList = [1, 3, 5, 7, 9];
        var myListItem = myList[3];
        // Act
        var searchedItemIndex = BinarySearcher.FindIndex(myList, myListItem);
        // Assert
        Assert.That(searchedItemIndex, Is.EqualTo(3));
    }

    [Test]
    public void BinarySearcher_Doesnt_Find_Item()
    {
        // Arrange
        int[] myList = [1, 3, 5, 7, 9];
        // Act
        var searchedItemIndex = BinarySearcher.FindIndex(myList, 10);
        // Assert
        Assert.That(searchedItemIndex, Is.EqualTo(-1));
    }
}

Mascarenas

Answer 7

public static object BinnarySearch(int[] array,int SearchKey)
    {
        int min = 0;
        int max = array.Length - 1;
        while (min <= max)
        {
            int mid = (min + max) / 2;
            if (SearchKey == array[mid])
            {
                return mid;
            }
            else if (SearchKey < array[mid])
            {
                max = mid - 1;
            }
            else
                min = mid + 1;
        }
        return "Not Found";
    }

Merna