矩陣搜索升級版

這個代碼很巧妙吁峻，相比原來的那個矩陣搜索更像是真正意義上的二分查找卖漫，亮點就是upper值得初始化和數(shù)組下標迭代更新。

實驗了下發(fā)現(xiàn)董飛老師的示例代碼是錯誤的仅父，while循環(huán)內matrix下標應為“[mid/n][mid%n]”教届，而非“[mid%m][mid%n]”

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int m = matrix.length;
        int n = matrix[0].length;

        if (target < matrix[0][0] || target > matrix[m-1][n-1])
            return false;


        int lower = 0;
        int upper = m*n -1;
        while (lower <= upper) {
            int mid = lower + (upper-lower)>>1;
            if (target == matrix[mid/n][mid%n]) {
                return true;
            } else if (target < matrix[mid/n][mid%n]) {
                upper = mid-1;
            } else {
                lower = mid+1;
            }
        }

        return false;
    }
}

Find Peak Element

原題地址
A peak element is an element that is greater than its neighbors.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

找到數(shù)組中的峰點，即這個數(shù)大于左右兩邊的數(shù)驾霜，示例代碼如下。

// A divide and conquer solution to find a peak element element
#include <stdio.h>

// A binary search based function that returns index of a peak element
int findPeakUtil(int arr[], int low, int high, int n)
{
    // Find index of middle element
    int mid = low + (high - low)/2;  /* (low + high)/2 */

    // Compare middle element with its neighbours (if neighbours exist)
    if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
            (mid == n-1 || arr[mid+1] <= arr[mid]))
        return mid;

    // If middle element is not peak and its left neighbor is greater than it
    // then left half must have a peak element
    else if (mid > 0 && arr[mid-1] > arr[mid])
        return findPeakUtil(arr, low, (mid -1), n);

    // If middle element is not peak and its right neighbor is greater than it
    // then right half must have a peak element
    else return findPeakUtil(arr, (mid + 1), high, n);
}

// A wrapper over recursive function findPeakUtil()
int findPeak(int arr[], int n)
{
    return findPeakUtil(arr, 0, n-1, n);
}

/* Driver program to check above functions */
int main()
{
    int arr[] = {1, 3, 20, 4, 1, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Index of a peak point is %d", findPeak(arr, n));
    return 0;
}