python算法之二分查找

說明：大部分代碼是在網上找到的，好幾個代碼思路總結出來的

通常寫算法，習慣用C語言寫，顯得思路清晰。可是假設一旦把思路确定下來，并且又不想打草稿。想高速寫下來看看效果，還是python寫的比較快。也看個人愛好。實習的時候有個同僚對于python的縮進來控制代碼塊各種噴。。。。他認為還是用大括号合适。。。怎麼說呢，适合自己的才是最好的。我個人的毛病就是，寫了幾天C，到要轉到python的時候，代碼中依舊有C的影子。。比方大括号問題，比方忘記在while或這for、if、else等後面加“：”。而假設寫了幾天Python，要轉到C的時候。會忘記聲明一些變量。直接拿來就用。執行的時候，各種變量沒有定義。在這裡給自己提個醒。多思考也要多動手。

今天無意中看到了二分查找。本來以為非常easy的代碼。幾行就結束了，後來看到了一個比較牛的代碼。才發現人比人該死是永恒的真理。為了不該死，也要把不該死的代碼學會才行啊，二分查找的原理非常easy，就是在一個有序序列中。查找代碼是一半一半的比較而不是一個一個的比較

最簡單的二分查找非遞歸代碼例如以下：

int search(int array[], int n, int v)
{
    int left, right, middle;

    left = 0, right = n - 1;

    while (left <= right)
    {
        middle = (left + right) / 2;
        if (array[middle] > v)
        {
            right = middle;
        }
        else if (array[middle] < v)
        {
            left = middle;
        }
        else
        {
            return middle;
        }
    }

    return -1;
}
           

輸入：array數組。array大小n，查找元素v

輸出：v的所在位置，沒有找到傳回-1

#####################################################################################################################################

以下寫個遞歸的代碼：

#include<stdio.h>

int search(int arr[],int low,int high,int key)
{
        int mid = (low+high)/2;
        if(low > high)
                return -1;
        if(arr[mid] == key)
                return mid;
        else if(arr[mid]>key)
                return search(arr,low,mid-1,key);
        else
                return search(arr,mid+1,high,key);
}
int main()
{
        int arr[101] = {1,2,3,4,87,90,100};
        int low = 0,high = 8,key = 87,ret;
        ret = search(arr,low,high,key);
        if(ret != -1)
                printf("the return is %d",ret);
        else
                printf("FBI warning:the return is -1,not find the key");
}
           

不知道遞歸的同學。請參考遞歸的吐槽。。。如圖：當年第一次聽到老師說遞歸的時候，想的就是這個

可是事實上遞歸是這種

好了不扯了。二分查找這個代碼事實上細緻看的話還是有點問題的。比方說這個三次推斷。兩次比較。還有就是

在循環體内,計算中間位置的時候,使用的是這個表達式:

mid = (left + right) / 2;

假如,left與right之和超過了所在類型的表示範圍的話,那麼middle就不會得到正确的值.

是以,更穩妥的做法應該是這種:

mid = left + (right - left) / 2; 那我們優化一下，python代碼例如以下：

def search(arr,n,v):
        left = -1
        right = n
        while(left+1 != right):
                mid = left+(right-left)/2
                if(arr[mid] < v):
                        left = mid
                else:
                        right = mid
        if(right >= n or arr[right] != v):
                right = -1
        return right
if __name__ == '__main__':
        arr = [1,2,4,23,87,90,555,1222,1444]
        n = len(arr)
        ret = search(arr,n,87)
        print ret
           

看C的代碼：

int search(int array[], int n, int v)
{
    int left, right, mid;

    left = -1, right = n;

    while (left + 1 != right)
    {
        mid = left + （right － left) / 2;

        if (array[mid] < v)
        {
            left = mid;
        }
        else
        {
            right = mid;
        }
    }

    if (right >= n || array[right] != v)
    {
        right = -1;
    }

    return right;
}
           

這個代碼先不說理不了解，光傳回值僅僅用right這個就非常牛逼，這樣看着非常easy，可是非常精髓的感覺有沒有？再看while的推斷，left+1!=right是不是非常正點？自己了解ba

轉載于:https://www.cnblogs.com/mengfanrong/p/5185668.html