22°

C# 二分法的解读

注:一定是有序的数组,才可以使用这种算法,如果数组没有排序则先进行排序后再调用此方法。

1、二分法是做什么的呢?

当然是查找数组中的数据了,开个玩笑,哈哈哈。

2、为啥要用这种方式呢?

二分顾名思义,就是将一组数据对半分开(比如左右两部分,下面用左右数组表示),从中间位置开始查找,

如果中间这个值正是咱们要找的值则直接返回这个值(或者索引),如果没有找到,那么去判断中间的这个值和咱们要找的值哪个大,

如果中间值比咱们要找的值大,则将之前分开的数组的左面的数组再进行对半分开,递归直到找到咱们要的那个值才会结束,反之亦然,

但是如果就是没有咱们找的那么岂不是死循环了嘛,

所以要加判断,如果递归到开始索引小于等于结束索引,则退出。

 

这种搜索算法每一次比较都使搜索范围缩小一半,这样对于大数据量的数组,极大的提升了查找效率。

 

private void button1_Click(object sender, EventArgs e)
        {
            int[] arry = { 8, 15, 19, 23, 26, 31, 40, 65, 91 };
            //测试  要找的数字是15
            int key = 15;
            //查找数并返回 若有,返回该数,没有则返回-1
            int rr = BinarySearch(arry, 0, arry.Length - 1, key); 
        }
    </span><span style="color: #808080;">///</span> <span style="color: #808080;">&lt;summary&gt;</span>
    <span style="color: #808080;">///</span><span style="color: #008000;"> 二分法查找指定值
    </span><span style="color: #808080;">///</span> <span style="color: #808080;">&lt;/summary&gt;</span>
    <span style="color: #808080;">///</span> <span style="color: #808080;">&lt;param name="arr"&gt;</span><span style="color: #008000;">目标数组</span><span style="color: #808080;">&lt;/param&gt;</span>
    <span style="color: #808080;">///</span> <span style="color: #808080;">&lt;param name="low"&gt;</span><span style="color: #008000;">开始索引</span><span style="color: #808080;">&lt;/param&gt;</span>
    <span style="color: #808080;">///</span> <span style="color: #808080;">&lt;param name="high"&gt;</span><span style="color: #008000;">结束索引</span><span style="color: #808080;">&lt;/param&gt;</span>
    <span style="color: #808080;">///</span> <span style="color: #808080;">&lt;param name="key"&gt;</span><span style="color: #008000;">要查找的关键字</span><span style="color: #808080;">&lt;/param&gt;</span>
    <span style="color: #808080;">///</span> <span style="color: #808080;">&lt;returns&gt;&lt;/returns&gt;</span>
    <span style="color: #0000ff;">public</span> <span style="color: #0000ff;">static</span> <span style="color: #0000ff;">int</span> BinarySearch(<span style="color: #0000ff;">int</span>[] arr, <span style="color: #0000ff;">int</span> low, <span style="color: #0000ff;">int</span> high, <span style="color: #0000ff;">int</span><span style="color: #000000;"> key)
    {
        </span><span style="color: #0000ff;">int</span> mid = (low + high) / <span style="color: #800080;">2</span><span style="color: #000000;">;
        </span><span style="color: #0000ff;">if</span> (low &gt;<span style="color: #000000;"> high)
            </span><span style="color: #0000ff;">return</span> -<span style="color: #800080;">1</span>;<span style="color: #008000;">//</span><span style="color: #008000;">查找不到返回-1</span>
        <span style="color: #0000ff;">else</span><span style="color: #000000;">
        {
            Console.WriteLine(arr[mid]);
            </span><span style="color: #0000ff;">if</span> (arr[mid] ==<span style="color: #000000;"> key)
                </span><span style="color: #0000ff;">return</span> mid;<span style="color: #008000;">//</span><span style="color: #008000;">若查找到,返回该数</span>
            <span style="color: #0000ff;">else</span> <span style="color: #0000ff;">if</span> (arr[mid] &gt;<span style="color: #000000;"> key)
                </span><span style="color: #0000ff;">return</span> BinarySearch(arr, low, mid - <span style="color: #800080;">1</span><span style="color: #000000;">, key);
            </span><span style="color: #0000ff;">else</span> <span style="color: #0000ff;">return</span> BinarySearch(arr, mid + <span style="color: #800080;">1</span><span style="color: #000000;">, high, key);
        }
    }</span></pre> 
View Code

 

 

本文转载自博客园,原文链接:https://www.cnblogs.com/jcl-yy/p/12213749.html

全部评论: 0

    我有话说: