各种算法五

各种算法五

我们来看看基本的超找滴呀；

在我们的算法中，有一种叫做线性查找。

分为：顺序查找。

折半查找。

顺序查找：

这种非常简单，就是过一下数组，一个一个的比，找到为止。

ps 顺便看到一个go相关的博客，我记录一下：http://blog.csdn.net/tybaoerge/article/details/50392386

   //基本的顺序查找太简单，其实就是找到你想要的额匹配项了滴呀；
        public static void LookUp()
        {
            List<int> list = new List<int>() { 2, 3, 5, 8, 7 };
            var result = GetIndex(list, 3);
            if (result != -1)
                Console.WriteLine("索引位置为：" + result);
            else
                Console.WriteLine("没有找到！");
            Console.Read();


        }

        static int GetIndex(List<int> list, int key)
        {
            for (int i = 0; i < list.Count; i++)
            {
                if (key == list[i])
                    return i; //返回制定的索引滴呀；
            }
            return -1;
        }

分半查找方式滴呀；这种方式，仅仅限于我们的奇数个值滴呀；可惜了~~~

      static int GetIndex01(List<int> list, int key)
        {
            //这种方式就要分我们的奇数个还是我们的偶数个了滴呀；
            //这个折半，也是那么简单的折半滴呀；
            var len = list.Count;
            var half = list.Count / 2;
            for (int i = 0; i < half; i++)
            {
                //其实这种比较的没有太大的比较，但依然可以看成是一种简单额优化吧；
                if (list[i] == key)
                {
                    return i;
                }
                if (list[len - 1-i] == key)
                {
                    return len - 1 - i;
                }
            }
            return -1;
        }

当然，我们可以进一步的各种优化滴呀；效果还是不错滴呀；

这样就算找到了我们比较通用的方法了；效果还是不错滴呀；恩恩，样滴呀；

       static int GetIndex02(List<int> list, int key)
        {
            //这种方式就要分我们的奇数个还是我们的偶数个了滴呀；
            //这个折半，也是那么简单的折半滴呀；
            var len = list.Count;
            var low = 0;
            var high = (len - 1);
            for (int i = 0; i < len; i++)
            {
                if (low <= high)  //这样我们的查找就可以继续滴呀；
                {
                    if (list[low] == key)
                    {
                        return low;
                    }
                    else
                    {
                        low++;
                    }
                    if (list[high] == key)
                    {
                        return high;
                    }
                    else
                    {
                        high--;
                    }
                }
              
            }
            return -1;
        }

总结：

如果使用平法的话；就会出现下面额情况滴呀；
如果是偶数的话，那么就敲好评分了；
如果是奇数的话，那么就会出现左右相差一的情况；

如果是low 和 high 两个指针的话，应该就是
左右两边刚好相等；
如果是奇数的话，low 和high 会指到统一index，然后再比较；
效果非常好的呀；

折半查找

使用折半查找是必须有前提滴呀；

第一：数组必须有序，不是有序就必须让其有序，大家也知道最快的排序也是NLogN的，所以.....呜呜。

第二：这种查找只限于线性的顺序存储结构。

好了，继续敲代码，ps，今天是星期五，好吧~

//上面的查找，技术含量太低了一点底呀；
        //是灰常滴呀；

        public static int ContinuteLookUpInformation()
        {
            //这个典型的缺点就是我们的表，必须是有序的表滴哎呀；
            //并且插入和删除是由困难的，因为你要维持他的“顺序”滴呀；
            //这里的折半，如果是奇数和偶数的数组呢？
            //这些都是很有趣的各种算法滴呀；
            List<int> list = new List<int>() { 3, 7, 9, 10, 11, 24, 45, 66, 77 };
            int key = 10;
            int low = 0;
            int high = list.Count - 1;
            while (low <= high)
            {
                //取出中间的额值；
                int middle= (low + high) / 2;
                if (list[middle] == key)
                {
                    return middle; //返回数组下标
                }else
                {
                    if (list[middle] > key)  //确定指针钱移 还是 后移的关键滴呀；
                    {
                        //到前面去找
                        high = middle - 1;
                    }else
                    {
                        low = middle + 1;
                        //到后去找滴哎呀；
                    }
                }

            }
            return -1;//没有找到我们想要的值滴呀；

        }

这里补充一个，关于数组，奇数后偶的折半问题；

x奇数: 1 2 3 4 5

y偶数：1 2 3 4

x/2=2;

y/2=2;

因为都是int 类型的；

x，第一次比较的正好是3

第二次， low=0 high=1; (low+hig)/2=0 如果还没找到到 (low+high)=1

这样左右两个数都比较了；

实现的方式也是多种多样滴呀；