已排序数组的二分查找

发布于 2024-12-14 15:24:42 字数 779 浏览 0 评论 0原文

我正在尝试使用此二进制搜索代码搜索降序排序的数组。然而,在我对它进行排序并尝试搜索之后,它没有返回任何结果,只是一个加载图标,它永远不会消失,就好像它有一个无限循环一样。我不确定问题是什么,因为代码看起来合乎逻辑。

这是4.0框架的aspx,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];

        }

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

        }

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(7

分開簡單 2024-12-21 15:24:42

Array 类中有一个二分搜索:

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

对于降序排列,可以使用 ReverseComparer 轻松完成,它很容易编写如下:

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

那么:

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 标志来保持算法的纯粹性,而不是将查找与输出问题混合在一起,这也将使您更容易知道如果退出循环而未找到会发生什么:

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

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";
红尘作伴 2024-12-21 15:24:42

在黑暗中拍摄:

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

我怀疑你在 mid+1 和 mid-1 之间来回跳动

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

夜未央樱花落 2024-12-21 15:24:42

这是一个正确的:

如果目标< mynumbers[mid] 那么你必须把最后一个带到 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;

            }

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;

            }
不忘初心 2024-12-21 15:24:42
//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);
     }
}
//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);
     }
}
违心° 2024-12-21 15:24:42

它对我有用

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

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;
}
巷子口的你 2024-12-21 15:24:42

.NET 8 中使用 C# 12 进行二分搜索。

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

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

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));
    }
}
谢绝鈎搭 2024-12-21 15:24:42
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";
    }
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";
    }
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文