11.二分查找的實現(xiàn)與特性

二分查找的前提

目標函數(shù)單調(diào)性（單調(diào)遞增或者遞減）
存在上下界（bounded）
能夠通過索引訪問（index accessible）

這三個前提條件的話簡單說來，一定要把它形成肌肉式記憶。

第一單調(diào)性：二分查找的是在有序的里面進行查找齐邦，如果它是無序的話記憶沒法進行二分查找析恋，無序的話怎么辦呢？只能從頭到尾遍歷，正因為它是有序的，所以能夠通過判斷它的某些特征排除掉比如說前半部分或者排除掉后半部分，所以這里它必須是要單調(diào)的到涂。
第二上下界：存在一個上下界，如果沒有上下界的話颁督，那么它的空間可能是無窮大的践啄，那么它就沒法往中間擴，當然也有特殊的形態(tài)沉御。
第三索引：索引的話指的是可以用下標進行訪問屿讽，所以很多時候如果是單鏈表的話，相對來說即使是有序的吠裆，單鏈表進行二分查找都不是那么容易的伐谈，當然如果把單鏈表進行一些改造，比如說用它所謂的跳表的方式试疙，那就另當別說了诵棵。

代碼模版

// Java
public int binarySearch(int[] array, int target) {
    int left = 0, right = array.length - 1, mid;
    while (left <= right) {
        mid = (right - left) / 2 + left;

        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return -1;
}

# Python
left, right = 0, len(array) - 1 
while left <= right: 
      mid = (left + right) / 2 
      if array[mid] == target: 
            # find the target!! 
            break or return result 
      elif array[mid] < target: 
            left = mid + 1 
      else: 
            right = mid - 1

C/C++

int binarySearch(const vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size()-1;
    
    while (left <= right) {
        int mid = left + (right - left)/ 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1;
}

/* JavaScript */
let left = 0, right = len(array) - 1
while (left <= right) {
  let mid = (left + right) >> 1
  if (array[mid] === target) { /*find the target*/; return }
  else if (array[mid] < target) left = mid + 1
  else right = mid - 1
}

首先左右界，分別是 $0$ 和 $數(shù)組長度減1$ 祝旷，也就是左右的下標值履澳，這個毋庸置疑嘶窄，while 的話里面是 left 小于等于 right 所以這個條件的話有些時候會變成沒有等于號，但是大部分情況下你可以認為是有小于等于的距贷。

然后得到它的中間值柄冲，就是 mid 這個值，判斷 mid 是否等于等于 target储耐，然后來 break 或者是 return 這個 result，可以先把等于等于放在這里滨溉，只要它等于的話就馬上 return 即可什湘。

在這里的話我們假設是上升的就是升序排列的，如果 target 大于 array[mid] 的話說明什么晦攒？說明它在右側闽撤，那么要繼續(xù)向右查找，所以 left 就把左界向右進行移動變成 $mid + 1$ 了脯颜，否則的話說明在這左側哟旗，那么右界的話就要向左移動變成 $mid - 1$ 這么一個形式。

那么根據(jù)這里所謂的左下界和右下界為整形的情況下栋操，就是為 Integer 的情況下闸餐，在有些時候可能為實數(shù)的情況下，那么就沒有所謂的加一或減一矾芙，在這個地方就直接等于 mid 即可舍沙。另外在有些特殊的情況，這里直接是小于的這種情況下剔宪，后面在例題的時候會大家一個更深刻的了解拂铡。

示例

在遞增數(shù)組里
[10, 14, 19, 26, 27, 31, 33, 35, 42, 44]
查找： $31$

它中間有些數(shù)是不連續(xù)的，但總體是單調(diào)遞增的葱绒，我們要查31這么查感帅，如果是正常遍歷的話，就是查這個一次兩次三次四次五次六次查找地淀，它的mid值算出來就等于31失球。那么用二分的話這么辦呢？

二分的話首先我們要查的是31帮毁，算它的中間值她倘，中間值剛才等于27，31 和 27 對比大于27作箍，說明可以排除前半部分硬梁，繼續(xù)從后半部分進行查找，繼續(xù)查找胞得，只要查后半部分了荧止，前半部分白色就不用考慮了，繼續(xù)在灰色部分查找。

灰色部分的中間繼續(xù)算跃巡，mid 的話就等于 35危号，查 35 的話比 35 小就說明繼續(xù)在 27 的右側 35 的左側開始找，就在這個數(shù)組里面開始找素邪。它的 mid 值又算出來等于 33外莲，它小于 33 ，再繼續(xù)往左邊找兔朦，最后就找到了 31 這個數(shù)偷线。

所以它是油左右兩個邊界不斷地向中間進行夾逼的過程，這種夾逼的過程又由于這個數(shù)組本身它是單調(diào)遞增的沽甥，所以我們每次可以排除一半声邦，你可以認為有點像二叉搜索樹一樣的特性，但這里的是用數(shù)組來進行實現(xiàn)的摆舟，而二分查找本身這種有序性的話亥曹，很多時候在數(shù)學里面的話用得也特別多，恨诱。

部分圖片來源于網(wǎng)絡媳瞪，版權歸原作者，侵刪照宝。