算法 – 二分查找
二分查找又称折半查找。时间复杂度O(log2n)。
注意:须是有序元素列表。
1. 比较次数少,查找速度快,平均性能好。
2. 插入、删除困难,比较适合不经常变动而查找频繁的有序列表。
思路:
每次都从元素列表中间开始查找。
1. 如果搜索数等于中间数,则直接返回中间数位置,停止搜索。
2. 如果搜索数大于中间数,则继续在大于中间数的元素中折半搜索,依次循环,直至找到或者搜索完毕。
3. 如果搜索数小于中间数,则继续在小于中间数的元素中折半搜索,依次循环,直至找到或者搜索完毕。

第一种写法:

public static string SearchIndex(int[] arrays , int txt)
{
    //数据头
    int start = 0;
    //数据尾
    int end = arrays.Length - 1;
    //中间位置
    int mid = end / 2;
    //查找次数
    int count = 0;

    while (start <= end)
    {
        count++;

        mid = (start + end) / 2;

        if (arrays[mid] == txt)
        {
            Console.WriteLine("查找次数" + count);
            return (mid + 1).ToString();
        }

        if (arrays[mid] > txt)
        {
            end = mid - 1;
            continue;
        }

        if (arrays[mid] < txt)
        {
            start = mid + 1;
        }
    }

    Console.WriteLine("查找次数" + count);
    return "null";
}

第二种写法:

public static string SearchIndexRecursion(int[] arr , int start , int end , int txt)
{
    sum++;

    if (start > end)
    {
        return "null";
    }

    //中间数
    int mid = (start + end) / 2;

    if (arr[mid] == txt)
    {
        Console.WriteLine("递归调用次数:" + sum);
        return (mid + 1).ToString();
    }

    if (arr[mid] > txt)
    {
        return SearchIndexRecursion(arr, start, mid - 1, txt);
    }

    if (arr[mid] < txt)
    {
        return SearchIndexRecursion(arr, mid + 1, end, txt);
    }

    return "ERROR";
}

完毕!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

wJie博客 – 个人博客 is Stephen Fry proof thanks to caching by WP Super Cache