Binary Search模板

在刷leetcode的過程中，各式各樣的Binary search代碼好難背呀，有沒有一個模板來應對所有binary search的問題呢？

首先我們要將問題分類，基本上Binary search問題，可以分成兩種問題

在sorted list中找到指定的數字並回傳該數字的index，如果沒找到回傳-1
在sorted list中找到符合條件的第一個元素位置

舉例來說，有一個list

int[] list = new int[]{1,3,5,7,9}

在這個list中找到數字為5並回傳其index，以這個例子來說就是屬於第一類的問題，這種類型就是長這樣沒有其他的樣子了，非常好辨識。

int index1 = binarySearchType1(list, 5)
int index2 = binarySearchType1(list, 6)
// index1 = 2
// index2 = -1

如果今天要改成找到第一個比6大的數，那就是屬於第二種類型，第二類型的list需要滿足一個特性，有一個判別式 fun()與一個定值k，滿足下面的條件

fun(i) = true if i >= k;
fun(i) = false if i < k;
where 0 <= i <= n, n = list.size;

以圖例來說如下，list中黃色的部分，判別式為True，反之為False

透過binarySearch可以找出由0開始第一個符合判別式的index，注意，如果list中都沒有符合判別式的index，那會回傳n，所以這種binarySearch適用範圍非常廣，舉例來說，最新的提交被測試發現一個嚴重的bug，但是上一次測試版本沒有這問題，假設中間已經有n筆提交，以這個例子來說，某一筆提交k，是引入問題的點，k以後的版本都有問題，k之前的版本沒有問題，符合第二種類型的特性，這時就可以用binary search第二種模版來找出k

以下就是模板

在sorted list中找到指定的數字並回傳該數字的index，如果沒找到回傳-1

// list is sorted by ascendent
public int binarySearch(int[] list, int target) {
 int left = 0;
 int right = list.length - 1;
 while (left <= right) {
     int mid = left + (right - left) / 2;
     if (list[mid] == target) {
         return mid;
     } else if (list[mid] > target) {
         right = mid - 1;
     } else {
         left = mid + 1;
     }
 }
 return -1;
}

在sorted list中找到符合條件的第一個元素位置

// fun 可以是一個函數，或者是一個判別式，如list[i] > 6
public int binarySearch(int[] list) {
 int left = 0;
 int right = list.length;
 while(left < right) {
     int mid = left + (right - left) / 2;
     if (fun(mid)) {
         right = mid;
     } else {
         left = mid + 1;
     }
 }
 return left;
}

基本觀念已經講完了，再來就是進階題，看看能不能轉過來，假設有一個非嚴格遞增的數列，請找出數字3的index，假如有很多個，回傳最後一個3出現的index。

int[] list = int[]{1, 2, 3, 3, 3, 3, 4, 5, 6};
int target = 3;

乍看之下可能會覺得是第一個類型，其實是第二種類型，第一個類型會找到一個3回傳他的index，無法指定是最後一個3，使用第二類型要先把題目換句話說，找出第一個大於target 3的index，然後再回來check前一個數是否是3。

public int findLastTarget(int[] list, int target) {
    int left = 0;
    int right = list.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (list[mid] > 3) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    // list最小的數字都大於target，代表list中沒有等於target的數字
    if (left == 0) {
        return -1;
    } else if (list[left - 1] == target) {
        return left - 1;
    } else {
        // 比target大的第一個數字，前一個數字不是target，也就代表list中沒有target.
        return -1;
    }
}

最後可以試一下如果今天改成要找到第一個3要怎麼找呢？提示一樣是使用第二個模板。