[数据结构与算法]线性查找与优化-二分法

这是我第一篇分享，纪念一下；

线性查找，也叫线性搜索：

我的理解就是在一个数组里面查找你想要的那个数字的下标，如果没有咱们以返回-1来表示；

思路：

遍历整个数组，一个for循环结束，输出所需要的下标

代码如下：

#include <stdio.h>
int search(int k,int len,int a[])//搜索函数，k是我们要找的数，len是不确定的数组长度，a[]是我们的数组
{
    int i;
    int r=-1;//如果没有就是-1
    for (i=0;i<len;i++)//简单的遍历，不多赘述；
    {
        if (a[i]==k)
        {
            r = i;//此处有细节，我会放两个代码作一比较；
            break;//查找完记得跳出循环；
        }
    }
    
    return r;
}

下来看这个代码

#include <stdio.h>
int search(int k,int len,int a[])
{
    int i;
    int r=-1;
    for (i=0;i<len;i++)
    {
        if (a[i]==k)
        {   return i;//此处多了一个return，把赋值环节去掉了
            
            break;
        }
    }
    
    return -1;
}

这里我说一下单一出口原则

单一出口原则是一个函数里面只有末尾一个return（或者void函数完全没有return而在最后一个语句之后自动返回）

也可以说：我们第一个代码只有一个return，而后续对代码返回值的改动可以更简便。举个做不到单一出口的例子，返回值是一些标志，比如错误标志，因为出错了，所以要在出错的代码行结束，直接return ErrorCode。多个出错位置，多个return。（可以理解为随便大小便）

线性搜索看似简便，运气好点的话你可以在第一个数就找到，运气不好，1000000个数，你想想怎么样呢！

接下来简单的介绍我对二分查找的理解及代码；

定义：二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求数组必须采用有序数组，而且表中元素按关键字有序排列。

伪代码如下：

a[100]={1,3,4,5,6,11,23,26,56}
我们要找 5 ，先选取中间的数6，用6和5比较发现5在6前面，后半段数组去掉，
然后此时新数组={1,3,4,5,6}
mid=4;
然后比较4和5
新数组={4，5，6}
mid=5；
ok！

*有序数列

*对半查找，效率对于大数据极高；

eg：10个数-3次

100-7次，1000-10次，100000000-30次。。。。。。

函数代码如下：

int erfen(int k,int len,int a[])
{
    int ret=-1;//同样的咱们遵循单一出口原则，没找的就打印-1；
    //我们要求中间的数，所以得知道两边的数字，左->left,右->right
    int l=0;//数组的第一个元素下标
    int r=len-1;//最后元素的下标
    int mid=(r+l)/2;
    while(r>l)
        //我们知道右边的下标不可能小于左边的，所以循环终止的条件是r<l
    {
        if(a[mid]>k)//
        {
            r=mid-1;//中间的数大于要找的数，所以k在mid左边，此时令r=mid-1，把mid及其之后的数组扔掉，折半；
        }
        else if(a[mid]<k)
        {
            l=mid+1;//同理我们扔掉前面的数组，折半，在后半段数组里查找；
        }
        else if(a[mid]==k)
        {
            ret=mid;
            break;//over ！！
        }
    }
    return ret;
}

*此篇博客我只打出来了查找函数的主要部分，至于main函数我想大家都会！！！

总结：

这里我主要是讲述了二分查找的思想，对代码的理解仅仅是我展示的，希望有更优化的代码可以互相交流！！！