數字在排序陣列中出現的次數

思路

二分查找：

1. 利用二分查找找到一個符合條件的值，然后回圈搜索這個值前后重復的次數，(回圈搜索使得演算法一部分退化到O(m))，
   時間復雜度O(m+lgn)，空間復雜度O(1)，

2. 使用兩個修改判定的二分查找，分別找到數字第一次出現和最后一次出現的位置，（推薦）
   時間復雜度O(lgn)，空間復雜度O(1)，

3. 由于題目陣列的特殊性（int），可以分別對搜索值±0.5，然后使用二分查找搜索兩個值，（特殊）
   時間復雜度O(lgn)，空間復雜度O(1)，

代碼1

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0)    return 0;
        int cnt = 0;
        int low = 0;
        int mid = 0;
        int high = array.length - 1;
        while(low <= high) {
            mid = (low + high) / 2;
            if(array[mid] == k) {
                break;
            } else if(array[mid] < k) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        for(int i = mid - 1; i >= 0; i--) {
            if(array[i] == k) {
                cnt++;
            } else {
                break;
            }
        }
        for(int i = mid; i < array.length; i++) {
            if(array[i] == k) {
                cnt++;
            } else {
                break;
            }
        }
        return cnt;
    }
}

代碼2

public class Solution {
    private int biSearchfirst(int[] arr, int k, int low, int high, int mid) {
        while(low <= high) {
            mid = (low + high) / 2;
            if(arr[mid] == k) {
                if(mid == 0 ||  arr[mid-1]!=k) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            } else if(arr[mid] < k) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
    
    private int biSearchlast(int[] arr, int k, int low, int high, int mid) {
        while(low <= high) {
            mid = (low + high) / 2;
            if(arr[mid] == k) {
                if(mid == arr.length - 1 ||  arr[mid+1]!=k) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            } else if(arr[mid] < k) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
    
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0)    return 0;
        int first = biSearchfirst(array, k, 0, array.length - 1, 0);
        int last = biSearchlast(array, k, 0, array.length - 1, 0);
        if(first == -1 || last == -1)    return 0;
        return last - first + 1;
    }
}

代碼3

public class Solution {
    private int biSearch(int[] arr, double k) {
        int low = 0;
        int mid = 0;
        int high = arr.length - 1;
        while(low <= high) {
            mid = (low + high) / 2;
            if(arr[mid] < k) {
                low = mid + 1;
            } else {
                high = mid -1;
            }
        }
        return low;
    }
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0)    return 0;
        int left = biSearch(array, k - 0.5);
        int right = biSearch(array, k + 0.5);
        return right - left;
    }
}

筆記

二叉查找，while(low <= high)，若k存在：

• 此時搜索k-ε的值，無論是否存在，mid回傳的都是k的前一位，low回傳的是k，high回傳的是mid，
• 此時搜索k+ε的值，無論是否存在，mid回傳的都是k的后一位，high回傳的是k，low回傳的是mid，
• 所以代碼3里right-left實際上就是low2-low1 = k最后一次出現的后一位 - k第一次出現的位置，

若k不存在：k最后一次出現的后一位 等于 k第一次出現的位置，相當于插進來一個數，
所以二分法使用第三種代碼方法時，只需要用low或者high代替mid回傳就行，最后位置的逼近自然會完成，

總結，二分法搜索若存在，回傳mid，若不存在，則回傳low或者high(類比向上向下取整，同時取一個方向的選擇)，