高效算法——二分查找

今天又get到了好多新知识，和大家share一下吧。
折半查找
比如我买了一双鞋，你好奇问我多少钱，我说不超过300元。你还是好奇，你想知道到底多少，我就让你猜，你会 怎么猜？
答案：你每次猜中间数。
对吧，所以我们一般猜数字的时候都从中间猜，再根据大了或者小了调整。应用到算法上其实省去了好多麻烦，直接将查找范围缩小了将近一半，大大提高了运算效率。顾此算法非常高效，以下可供大家了解一下：

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int k = 7;

    int left = 0;
    int right = sizeof(arr)/sizeof(arr[0])- 1;
    int mid = 0; 

    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (arr[mid] < k)
        {
            left = mid + 1;
        }   
        else if (arr[mid]>k)
        {
            right = mid - 1;
        }
        else
        {
            printf("找到了，下标是：%d\n",mid);
            break;
        }
    }
    if (left > right)
        printf("找不到了\n");
    system("pause");
    return 0;
}

这个是一个简单的查找数组元素的方法，当然后续小洛会继续拓展，比如你输一个数组，再次查找你刚才所输入元素的下标，将再次进行代码优化。当然我们也可以将其设置为函数，更加方便我们调用。以下为函数模型：

int binary_search(int arr[], int k, int sz)
{
    int left = 0;
    int mid = 0;
    int right = sz - 1;

    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (arr[mid] < k)
        {
            left = mid + 1;
        }
        else if (arr[mid]>k)
        {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

如果我们查找到了这个元素的下标，就直接返回此下标，否则就返回-1。这样做使代码更加简洁，凝练。再附上main函数：

int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int k = 7;
    int sz = sizeof(arr) / sizeof(arr[0]) - 1;
    int ret = binary_search(arr,k ,sz);
    if (ret == -1)
    {
        printf("找不到呀!\n");
    }
    else
    {
        printf("找到了，下标是：%d", ret);
    }

    system("pause");
    return 0;

}

当让我们还可以再进行一下优化，这样使代码更加灵活。如：

int binary_search(int arr[], int k, int left,int right)
{
    int mid = 0;

    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (arr[mid] < k)
        {
            left = mid + 1;
        }
        else if (arr[mid]>k)
        {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

这样做我们可以对left和right进行修改，又可以提高一下效率。是不是非常使用呢？
下次小洛将带来更多知识，和大家一起成长。