算法：時間複雜度+二分查找法(Java

導讀

曾幾何時學好數據結構與算法是我們從事計算機相關工作的基本前提，然而現在很多程序員從事的工作都是在用高級程序設計語言（如Java）開發業務代碼，久而久之，對於數據結構和算法就變得有些陌生了，由於長年累月的碼磚的緣故，導致我們都快沒有這方面的意識了，雖然這種論斷對於一些平時特別注重學習和思考的人來說不太適用，但的確是有這樣的一個現象。

而在要出去面試找工作的時候，才發現這些基礎都快忘光光了，所以可能就“杯具”了！實際上，對於數據結構和算法相關的知識點的學習，是程序員必須修煉的一門內功，而要掌握得比較牢靠除了需要在寫代碼的時候時刻保持這方面的意識外，也需要日常的訓練，換一個目前比較流行的詞叫刻意練習。

這就像打乒乓球一樣，雖然大家都會打，但是要打得好，打出水準就得經常訓練。而學習算法的過程也是這樣，因為大部分人的腦容量有限，對於學過的算法知識雖然之前理解過，但是因為時間的關係和算法本身就是比較抽象的一種知識，所以容易忘記。那麼有沒有什麼好的練習工具呢？

在這裡給大家推薦一個練習數據結構和算法編程的網站：

https://leetcode.com（因為牆的原因，你可能需要搭個梯子，或者也可以訪問中文版的網站）這是一個目前很多硅谷的公司或程序員在學習或者招聘時都在使用的在線練習網站。上面有很多數據結構和算法的題，可以選擇不同的編程語言實現，還支持代碼社交，你提交的代碼可以被全世界的程序員看到並被評論，從而得到相應地反饋。

以本文將要講述的二分查找算法為例，在給大家的代碼示例中作者就在這個網站上使用Java/Go/Python三種語言進行了實現，如圖所示：

算法複雜度

因為小碼農是想做一個比較系統的總結，所以在給大家分享具體的算法內容之前，需要先和大家一起回顧下什麼是算法複雜度？

在編程的過程中，特別是寫一些比較基礎的邏輯代碼時，我們經常會討論說這段代碼的

時間複雜度是多少，空間複雜度是多少之類的術語。而這兩項指標就是我們衡量我們寫的代碼（任何代碼片段都可以視為算法）好壞最主要的兩個標準了，時間複雜度是說我們寫的這段代碼的運行時間，而空間複雜度則是在說這段代碼運行所佔用的內存空間大小。

一般來說，我們在選擇算法、編寫相應的代碼時都應該儘量選擇運行時間最快，內存空間佔用最少的方式。然而作為衡量算法好壞的標準，關於時間複雜度、空間複雜度如何衡量？目前是通過大O表示法來表示的，也就是我們經常說的O(xx)，例如O(1)、O(n)之類。

以下是我們常見的一些大O運行時間的表示（從快到慢）：

這是一種常數級的複雜度，這種複雜度的算法運行效率是最高的。例如，我們要計算“1+2+3+...+n”的和（假設n=100）？

如果我們採用如方式實現，那麼100類累加和的計算，這段代碼需要執行100次，1000累加和則需要執行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?上面這段程序都是需要執行一次，此時我們就可以說這段代碼的時間複雜度是O(1)了。

這是一種對數級的複雜度。可能上學的時候是因為體育老師教數學的緣故小碼農已經忘記什麼是對數了，在這裡和大家一起復習下，假如你忘記了對數的概念，但是冪的概念你一定還是記得的log8相當於在問“將多少個2相乘的結果為8”，正常來說log對數還有個下標，因為我們在討論算法複雜度時通常默認對數的下標為2，如2x2x2=8，所以log8=3。

那麼什麼樣的算法的時間複雜度是對數級的呢？後面我們即將討論的第一種算法（二分查找法）的時間複雜度就是對數級的，關於這塊的代碼示例，大家可以直接參考後面的示例。

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

O(n*logn)是O(logn)、O(n)兩種複雜度的一種組合，在後續的文章中要給大家介紹的“快速排序算法”(一種速度較快的排序算法)，其時間複雜度就是O(n*logn)，這裡大家可以暫時先放一下，等後面具體講述此算法時，可以體會下相應的代碼示例。

平方級的複雜度，在後續要介紹的算法中，“選擇排序算法”（一種速度較慢的算法）的時間複雜度就是這個級別的。如

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個元素比第m個元素小，將j賦值給m 

 if (arr[j] < arr[m]) {
 m = j;
 }
 }
 //交換m和i兩個元素的位置
 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(",");
 }
 }

階乘級的複雜度表示，時間複雜度為O(n!)的算法是一個非常慢的算法，例如斐波那契數列問題。如

 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");
 }
 }

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

二分查找法

在瞭解算法複雜度後，我們來介紹一個相對基礎的算法“二分查找法”！其輸入是一個有序的元素列表（必須有序）

，如果查找的元素包含在這個有序列表中，二分查找就會返回其位置，否則返回-1。

假設有一個1～100的數字：

目標是以最少的次數從這個100個數字中找到指定的數字。通常思路是，我們需要從1開始一個一個比較，如果指定的數字是100，那麼用這種傻找的方式需要找100次。如果範圍擴大到1000，查找1000，那麼相應地就需要找1000次，依次類推。

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

如果我們還是查找100的話，那麼50比100小，這樣我們就可以一次性排除前50個元素了，因為已經很明確的知道了前50個元素都比目標元素小了，這些元素也就沒有必要繼續參與比較了。

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

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

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

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

好了，到這裡就講完二分查找算法的基本原理了，那麼在具體的程序代碼中，二分查找算法應該如何實現呢？以下為大家準備了Java/Go/Python三種版本的實現，大家可以在leetcode上嘗試自己實現下。

#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
/<target>