7.二分搜索模板及变体（下）

---

矩阵搜索升级版

这个代码很巧妙，相比原来的那个矩阵搜索更像是真正意义上的二分查找，亮点就是upper值得初始化和数组下标迭代更新。

实验了下发现董飞老师的示例代码是错误的，while循环内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.

找到数组中的峰点，即这个数大于左右两边的数，示例代码如下。

// 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;
}

---