【算法】查找

整数二分

1. 如果单调一定可以二分
2. 二分不一定必须单调性

二分模板分为两种，在做题的时候，考虑一下check()条件，如果满足第一种情况需要将mid = (l+r+1)/2。

例如：

找到数列1 2 3 3 3 4中3的左右区间，显然是[2, 4]。

在二分查找的时候首先查找其左区间，找左区间就是即便x==arr[mid]，还是要将右指针j向左挪，而找右区间，即便x==arr[mid]，左指针i还是要向右挪。那么代码可以如下：

找左区间：

while(i < j) // 左下标
{
    mid = (i+j)/2;
    if(x > arr[mid]) // 如果3>arr[mid]，那么显然mid不再区间[2, 4]内，因此i=mid+1
        i = mid + 1;
    else
        j = mid;
}

此时得到的i则为左区间2。

找右区间：

while(i < j)
{
    mid = (i+j+1)/2; //这里的+1是为了防止死循环，例如i=3,j=4，如果不+1，将会死循环
    if(x >= arr[mid]) //如果3>=arr[mid]，显然mid是在区间内的，因此i=mid
        i = mid;
    else
        j = mid - 1;
}

二叉搜索树

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

// 从矩阵的右上角看这是一个二叉搜索树
func findNumberIn2DArray(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }
     i, j := 0, len(matrix[0]) - 1
     for i >=0 && i < len(matrix) && j >= 0 && j < len(matrix[0]) {
         if matrix[i][j] > target {
             j --
         } else if matrix[i][j] < target {
             i ++
         } else {
             return true
         }
     }
     return false
}