寻找与排序02,折半寻找

<?php
    /*
     *冒泡排序
     */
    function maopao($array){
        for($i =0;$i < count($array);$i++){
            for($j = $i+1;$j < count($array);$j++){
                if($array[$i] > $array[$j]){
                    $temp = $array[$i];
                    $array[$i] = $array[$j];
                    $array[$j] = $temp;
                }
            }
        }
        return $array;
    }

    /*
     * 二分查找
     */

    function erfen($array,$search,$low = 0,$hight = 100)
    {
        $midPostion = floor(($low + $hight)/2);
        $midData = $array[$midPostion];
        if($midData == $search)
        {
            return $midPostion;
        }
        if($search < $midData)
        {
            $hight = $midPostion;
            if($hight == 0)
            {
                return false;
            }
            return erfen($array,$search,$low,$hight);
        }else{
            $low = $midPostion + 1;
            if($low > $hight){
                return false;
            }
            return erfen($array,$search,$low,$hight);
        }
    }

    /*
     * 100+99+98+.......1;
     */

    function leijia($n)
    {
        if($n == 1){
            return $n;
        }
        return $n + leijia($n-1);
    }


    $a= array(9,4,6,8,2,4,5,1);
    $b= maopao($a);

    $c = array(1,2,3,4,5,6,7,8,9);
    $k = 5;
    $d = erfen($c,$k,0,8);

    $sum = leijia(100);
    echo $sum;

折半物色,也叫二分查找,当在贰个数组或集合中检索有些元素时,先稳住出中间地点元素,假若要寻找的因素正好和该中间地点成分相等,通过1遍搜索,就能找到匹配成分;假诺要物色的因素小于该中间地方成分,就放任前面5/10的要素,在日前五成的成分中再定位出中间地方成分,如此频仍,直到找到匹配成分;尽管要摸索的要素大于该中间地点元素,就放弃后面八分之四的因素,在末端50%的因素中定位出中间地点成分,如此频仍。

 

 

面临的首先个难点是:中间地方成分如何定位?在折半查找中规定:当成分个数是奇数,比如有一个因素,中间地点成分是索引为1的要素;当成分个数是偶数,比如有五个成分,索引为1和2的因素理论都以中等地方元素,但在折半查找中,把后边这些,即索引为2的成分正是中间地点成分。

 

面临的第二个问题是:由于,要寻找的因素和高级中学级地点成分之间供给相比,大家在可比前面,势须要让数组按升序或降序来排列。

 

自定义二个类,该类维护着3个int[]系列数组,通过构造函数分明数老板度和对数组实行排序,并提供打字与印刷数组成分的情势,以及折半算法。

    public class MyArray

    {

        private int[] arr;//内部维护着一个数组

        private static Random r = new Random();//用它来生成数组的随机元素

        //通过构造函数来确定内部数组的长度,并生成数组的随机元素,并对数组元素排序

        public MyArray(int size)

        {

            arr = new int[size];

            for (int i = 0; i < size; i++)

            {

                arr[i] = r.Next(1, 100);

            }

            Array.Sort(arr);

        }

        //折半查找算法 返回查找元素的索引位置

        public int HalfSearch(int key)

        {

            int low = 0;//低点,初始值设置成最低点,即索引0

            int high = arr.Length - 1;//高点,初始值设置成最高点,即索引数组最后一个位置

            //如果数组元素个数是偶数,比如4个,索引2和3都是中间位置,用以下算法中间位置指向索引3

            //如果数组元素个数是奇数,比如3个,索引1是中间位置,用以下算法中间位置指向索引1

            int middle = (low + high + 1)/2;

            int location = -1;//找不到就返回-1

            //循环,找不到就一直查找

            do

            {

                //每次循环,把低点和高点位置的元素打印出来

                Console.WriteLine(PrintSectionElements(low, high));

                Console.WriteLine();

                //如果要查找元素是中间位置的元素,就返回中间位置这个索引

                if (key == arr[middle])

                {

                    location = middle;

                }

                else if (key < arr[middle]) //如果要查找元素小于中间位置元素,把中间位置前面的索引设为高点

                {

                    high = middle - 1;

                }

                else//如果要查找元素大于中间位置元素,把中间位置后面的索引设为低点

                {

                    low = middle + 1;

                }

                //如果代码运行到此处,说明还没有找到匹配元素,由于以上重新设置了低点或高点,所以这里也要重新设置中间位置

                middle = (low + high + 1)/2;

            } while ((low <= high) && (location == -1));

            return location;

        }

        //打印2个位置间的数组元素

        public string PrintSectionElements(int low, int high)

        {

            string temp = "";

            //对于2个位置间的元素打印出元素并跟上一个空格位置

            for (int i = low; i <= high; i++)

            {

                temp += arr[i] + " ";

            }

            return temp;

        }

        //重写ToString方法,把数组所有的元素都打印出来

        public override string ToString()

        {

            return PrintSectionElements(0, arr.Length - 1);

        }

    }

如上,折半招来的目标是找到匹配成分在数组中的索引地点,为此,通过需寻找成分和中级地点成分大小的可比,不断地调动低点、高点和中路地点。其余,在C#中,八分之四的结果是0。

 

客户端。

    class Program

    {

        private static int key; //需查找元素

        private static int position;//匹配元素所在的位置

        static void Main(string[] args)

        {

            MyArray myArray = new MyArray(7);

            //把所有元素打印出来

            Console.WriteLine(myArray);

            Console.WriteLine("请输入需要查找的元素或输入-1退出 ");

            key = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine();

            while (key != -1)

            {

                //调用折半算法得出所需查找元素的位置

                position = myArray.HalfSearch(key);

                if (position == -1) //说明没有找到需要匹配的元素

                {

                    Console.WriteLine("没有找到元素{0}", key);

                }

                else

                {

                    Console.WriteLine("在{0}号位置查到元素{1}", position, key);

                }

                Console.WriteLine("请输入需要查找的元素或输入-1退出 ");

                key = Convert.ToInt32(Console.ReadLine());

                Console.WriteLine();

            }

        }

    }

图片 1

 

  用时间复杂度来描述折半招来的频率

假定二个数组有102贰个要素,由于能够象征成”1023=2ⁿ-1″等式,全数n=10。对该数组每进行1次折半,也等于除以2,也正是说,在该数组中查找有个别成分,最多须求十四遍,就能够查到匹配成分。

 

对于”2ⁿ-1″这一个表明式,当n=30,就意味着10亿,使用折半查找,10亿个要素最多必要叁十四回就能找到匹配成分。而利用线性查找需求平均5亿次的查找。2种算法的频率由此可见一斑。

 

把折半寻觅、二分查找的时光复杂度写成O(log
n),称为”对数运营时刻”,读为”对数阶”。

 

“查找与排序”种类包涵:

检索与排序01,线性查找,时间复杂度,算法

找寻与排序02,折半找寻

搜索与排序03,选取排序

追寻与排序04,插入排序

查找与排序05,冒泡排序

发表评论

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

网站地图xml地图