導(dǎo)讀

曾幾何時(shí)學(xué)好數(shù)據(jù)結(jié)構(gòu)與算法是我們從事計(jì)算機(jī)相關(guān)工作的基本前提，然而現(xiàn)在很多程序員從事的工作都是在用高級(jí)程序設(shè)計(jì)語言（如Java）開發(fā)業(yè)務(wù)代碼，久而久之，對于數(shù)據(jù)結(jié)構(gòu)和算法就變得有些陌生了，由于長年累月的碼磚的緣故，導(dǎo)致我們都快沒有這方面的意識(shí)了，雖然這種論斷對于一些平時(shí)特別注重學(xué)習(xí)和思考的人來說不太適用，但的確是有這樣的一個(gè)現(xiàn)象。

而在要出去面試找工作的時(shí)候，才發(fā)現(xiàn)這些基礎(chǔ)都快忘光光了，所以可能就“杯具”了！實(shí)際上，對于數(shù)據(jù)結(jié)構(gòu)和算法相關(guān)的知識(shí)點(diǎn)的學(xué)習(xí)，是程序員必須修煉的一門內(nèi)功，而要掌握得比較牢靠除了需要在寫代碼的時(shí)候時(shí)刻保持這方面的意識(shí)外，也需要日常的訓(xùn)練，換一個(gè)目前比較流行的詞叫刻意練習(xí)。

這就像打乒乓球一樣，雖然大家都會(huì)打，但是要打得好，打出水準(zhǔn)就得經(jīng)常訓(xùn)練。而學(xué)習(xí)算法的過程也是這樣，因?yàn)榇蟛糠秩说哪X容量有限，對于學(xué)過的算法知識(shí)雖然之前理解過，但是因?yàn)闀r(shí)間的關(guān)系和算法本身就是比較抽象的一種知識(shí)，所以容易忘記。那么有沒有什么好的練習(xí)工具呢？

在這里給大家推薦一個(gè)練習(xí)數(shù)據(jù)結(jié)構(gòu)和算法編程的網(wǎng)站：

https://leetcode.com（因?yàn)閴Φ脑?，你可能需要搭個(gè)梯子，或者也可以訪問中文版的網(wǎng)站）這是一個(gè)目前很多硅谷的公司或程序員在學(xué)習(xí)或者招聘時(shí)都在使用的在線練習(xí)網(wǎng)站。上面有很多數(shù)據(jù)結(jié)構(gòu)和算法的題，可以選擇不同的編程語言實(shí)現(xiàn)，還支持代碼社交，你提交的代碼可以被全世界的程序員看到并被評論，從而得到相應(yīng)地反饋。

以本文將要講述的二分查找算法為例，在給大家的代碼示例中作者就在這個(gè)網(wǎng)站上使用Java/Go/Python三種語言進(jìn)行了實(shí)現(xiàn)，如??圖所示：

算法復(fù)雜度

因?yàn)槲沂窍胱鲆粋€(gè)比較系統(tǒng)的總結(jié)，所以在給大家分享具體的算法內(nèi)容之前，需要先和大家一起回顧下什么是算法復(fù)雜度？

在編程的過程中，特別是寫一些比較基礎(chǔ)的邏輯代碼時(shí)，我們經(jīng)常會(huì)討論說這段代碼的時(shí)間復(fù)雜度是多少，空間復(fù)雜度是多少之類的術(shù)語。而這兩項(xiàng)指標(biāo)就是我們衡量我們寫的代碼（任何代碼片段都可以視為算法）好壞最主要的兩個(gè)標(biāo)準(zhǔn)了，時(shí)間復(fù)雜度是說我們寫的這段代碼的運(yùn)行時(shí)間，而空間復(fù)雜度則是在說這段代碼運(yùn)行所占用的內(nèi)存空間大小。

一般來說，我們在選擇算法、編寫相應(yīng)的代碼時(shí)都應(yīng)該盡量選擇運(yùn)行時(shí)間最快，內(nèi)存空間占用最少的方式。然而作為衡量算法好壞的標(biāo)準(zhǔn)，關(guān)于時(shí)間復(fù)雜度、空間復(fù)雜度如何衡量？目前是通過大O表示法來表示的，也就是我們經(jīng)常說的O(xx)，例如O(1)、O(n)之類。

以下是我們常見的一些大O運(yùn)行時(shí)間的表示（從快到慢）：

這是一種常數(shù)級(jí)的復(fù)雜度，這種復(fù)雜度的算法運(yùn)行效率是最高的。例如，我們要計(jì)算“1+2+3+...+n”的和（假設(shè)n=100）？

如果我們采用如??方式實(shí)現(xiàn)，那么100的累加和的計(jì)算，這段代碼需要執(zhí)行100次，1000累加和則需要執(zhí)行1000次。

 public static void main(String args[]) {

       int y = 0;
       for (int i = 0; i <= 100; i++) {
           y = i + y;
       }
       System.out.println(y);
   }

而如果我們換種方式如??

  public static void main(String args[]) {

        int y = 0;
        y = 100 * (100 + 1) / 2;
        System.out.println(y);
    }

那么無論多少的累加和，10000、100000、100000?上面這段程序都是需要執(zhí)行一次，此時(shí)我們就可以說這段代碼的時(shí)間復(fù)雜度是O(1)了。

這是一種對數(shù)級(jí)的復(fù)雜度?？赡苌蠈W(xué)的時(shí)候是因?yàn)轶w育老師教數(shù)學(xué)的緣故小碼農(nóng)已經(jīng)忘記什么是對數(shù)了，在這里和大家一起復(fù)習(xí)下，假如你忘記了對數(shù)的概念，但是冪的概念你一定還是記得的log8相當(dāng)于在問“將多少個(gè)2相乘的結(jié)果為8”，正常來說log對數(shù)還有個(gè)下標(biāo)，因?yàn)槲覀冊谟懻撍惴◤?fù)雜度時(shí)通常默認(rèn)對數(shù)的下標(biāo)為2，如2x2x2=8，所以log8=3。

那么什么樣的算法的時(shí)間復(fù)雜度是對數(shù)級(jí)的呢？后面我們即將討論的第一種算法（二分查找法）的時(shí)間復(fù)雜度就是對數(shù)級(jí)的，關(guān)于這塊的代碼示例，大家可以直接參考后面的示例。

O(n)是一種線性的時(shí)間復(fù)雜度，如前面我們在說0(1)時(shí)，如果計(jì)算累加和的操作采用第一種方式，那么100的累加和需要執(zhí)行100次，1000的累加和就需要執(zhí)行1000次，以此類推，這樣的時(shí)間復(fù)雜度就稱之為O(n)。

O(nlogn)是O(logn)、O(n)兩種復(fù)雜度的一種組合，在后續(xù)的文章中要給大家介紹的“快速排序算法”(一種速度較快的排序算法)，其時(shí)間復(fù)雜度就是O(nlogn)，這里大家可以暫時(shí)先放一下，等后面具體講述此算法時(shí)，可以體會(huì)下相應(yīng)的代碼示例。

平方級(jí)的復(fù)雜度，在后續(xù)要介紹的算法中，“選擇排序算法”（一種速度較慢的算法）的時(shí)間復(fù)雜度就是這個(gè)級(jí)別的。如??

public static void main(String args[]) {

       int[] arr = new int[]{4, 1, 3, 2, 6, 7, 8};
       for (int i = 0; i < arr.length; i++) {
           int m = i;
           for (int j = i + 1; j < arr.length; j++) {
               //如果第j個(gè)元素比第m個(gè)元素小，將j賦值給m
               if (arr[j] < arr[m]) {
                   m = j;
               }
           }
           //交換m和i兩個(gè)元素的位置
           if (i != m) {
               int t = arr[i];
               arr[i] = arr[m];
               arr[m] = t;
           }
       }

       for (int i = 0; i < arr.length; i++) {
           System.out.print(arr[i]);
           System.out.print(",");

       }

   }

階乘級(jí)的復(fù)雜度表示，時(shí)間復(fù)雜度為O(n!)的算法是一個(gè)非常慢的算法，例如斐波那契數(shù)列問題。如??

 public static int fib(int num) {
        if (num == 1 || num == 2) {
            return 1;
        } else {
            return fib(num - 2) + fib(num - 1);
        }
    }

    public static void main(String[] args) {

        for (int i = 1; i <= 6; i++) {
            System.out.print(fib(i) + "\t");
        }
    }

以上就是我們在討論算法復(fù)雜度時(shí)大部分的表示方法了，需要說明的是算法的速度并非單單指時(shí)間，而是操作數(shù)的增速，說的是隨著輸入的增加，其運(yùn)行時(shí)間將以什么樣的速度增加，例如O(log n)比O(n)快，當(dāng)需要搜索的元素越多時(shí)，O(log n)比O(n)快得越多。

二分查找法

在了解算法復(fù)雜度后，我們來介紹一個(gè)相對基礎(chǔ)的算法“二分查找法”！其輸入是一個(gè)有序的元素列表（必須有序），如果查找的元素包含在這個(gè)有序列表中，二分查找就會(huì)返回其位置，否則返回-1。

假設(shè)有一個(gè)1～100的數(shù)字：

目標(biāo)是以最少的次數(shù)從這個(gè)100個(gè)數(shù)字中找到指定的數(shù)字。通常思路是，我們需要從1開始一個(gè)一個(gè)比較，如果指定的數(shù)字是100，那么用這種傻找的方式需要找100次。如果范圍擴(kuò)大到1000，查找1000，那么相應(yīng)地就需要找1000次，依次類推。

很顯然，這種方式不是很靠譜。那么有沒有更好的方法呢？這就是我們要說的二分查找法了，它的思路是先從元素的中間開始查找，如直接查找第50(第一次)個(gè)元素，比較中間元素與目標(biāo)元素之間的大小。

如果我們還是查找100的話，那么50比100小，這樣我們就可以一次性排除前50個(gè)元素了，因?yàn)橐呀?jīng)很明確的知道了前50個(gè)元素都比目標(biāo)元素小了，這些元素也就沒有必要繼續(xù)參與比較了。

第二次，我們從51～100之間再取中間元素進(jìn)行判斷，取75進(jìn)行判斷，75依然比100小，那么51～75這一段的數(shù)字也就直接排除掉了。

第三次，我們從76～100之間取中間元素，88，88<100；第四次，繼續(xù)查找取89～100之間的中間元素95，95<100；第五次，繼續(xù)取96～100中間元素98，98<100；第六次，繼續(xù)取99～100之間的中間元素100，100=100，完成查找。

通過這種方式，我們總共運(yùn)行了6次就完成了查找動(dòng)作，相比之前的100次查找要靠譜，而這就是二分查找算法的基本原理了。

按照這種方式，即使列表中包含40億個(gè)有序元素，最多也只需要32次就能完成查找。所以如果用前面描述的大O表示法，表示二分查找算法的時(shí)間復(fù)雜度是O(log n)。

好了，到這里就講完二分查找算法的基本原理了，那么在具體的程序代碼中，二分查找算法應(yīng)該如何實(shí)現(xiàn)呢？以下為大家準(zhǔn)備了Java/Go/Python三種版本的實(shí)現(xiàn)，大家可以在leetcode上嘗試自己實(shí)現(xiàn)下。

#Java

public class Solution {

    public static int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        int middle;
        while (low <= high) {
            middle = (low + high) / 2;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] < target) {
                low = middle + 1;
            } else{
                high = middle - 1;
            } 
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int result1 = search(nums, 9);
        int result2 = search(nums, 2);
        System.out.println("result is->" + result1);
        System.out.println("result is->" + result2);
    }
}

#Go

package main

import (
    "fmt"
)

func main() {
    nums := []int{-1, 0, 3, 5, 9, 12}
    result := search(nums, 2)
    fmt.Println(result)
}

func search(nums []int, target int) int {
    low, high, middle := 0, len(nums)-1, -1
    for low <= high {
        middle = (low + high) / 2
        if nums[middle] == target {
            return middle
        } else if nums[middle] < target {
            low = middle + 1
        } else {
            high = middle - 1
        }
    }
    return -1
}

#Python

class Solution:
    def search(result,nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        low,high,middle=0,len(nums)-1,-1
        while low<=high:
           middle=(low+high)//2
           if nums[middle]==target:
               return middle
           elif nums[middle]<target:
               low=middle+1
           else:
               high=middle-1
        return -1