套路

• 查找時：拒絕依次探查這種低效的做法，要么使用二分查找，要么使用哈希表一次查出結(jié)果。
• 數(shù)列整體有序或者部分有序就要第一時間想到二分查找

注意點

• 二分查找寫法按這種方式： int mid = low + (high - low) / 2; 防止因為 low + high 超出int值的范圍而出錯。

目錄

• 二維數(shù)組中的查找
• 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

二維數(shù)組中的查找

在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

• 最優(yōu)解：選擇從左下角或右上角開始查找，每次沒找到目標元素時可以直接排除一行或一列，從而在最短時間內(nèi)得到結(jié)果

public boolean Find(int target, int [][] array) {
    if (array == null || array[0] == null) {
        return false;
    }
    int rows = array.length, cols = array[0].length;
    int i = 0, j = cols - 1;
    while (i < rows && j >= 0) {
        if (target < array[i][j]) {
            j--;
        } else if (target > array[i][j]) {
            i++;
        } else {
            return true;
        }
    }
    return false;
}

數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

• 二分查找到其中一個k，再往左右探查，但是依然是挨個遍歷，還不是最優(yōu)。
• 數(shù)組有序，二分查找找到第一個出現(xiàn)k的位置和最后一個出現(xiàn)k的位置，返回差+1即可。

public int GetNumberOfK(int [] array , int k) {
    if (array == null || array.length == 0) {
        return 0;
    }
    int first = findFirstK(array, k, array.length - 1);
    int last = findLastK(array, k, array.length - 1);
    return first == -1 ? 0 : last - first + 1;
}

private int findFirstK(int[] array, int k, int last) {
    int low = 0, high = last;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (array[mid] < k) {
            low = mid + 1;
        } else if (array[mid] == k && (mid == 0 || array[mid - 1] < array[mid])) {
            return mid;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

private int findLastK(int[] array, int k, int last) {
    int low = 0, high = last;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (array[mid] > k) {
            high = mid - 1;
        } else if (array[mid] == k && (mid == last || array[mid] < array[mid + 1])) {
            return mid;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}