算法-二分查找

什么是二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，可以在数据规模的对数时间复杂度内完成查找。算法。

二分查找可以应用于数组，是因为数组具有有随机访问的特点，并且数组是有序的。

二分查找体现的数学思想是「减而治之」，可以通过当前看到的中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果。

算法实现

首先，假设数组中元素是按升序排列，将数组中间位置记录的值与查找目标值比较，如果两者相等，则查找成功；否则利用中间位置值将数组分成前、后两个子数组，如果中间位置记录的值大于查找目标值，则进一步查找前一子数组，否则进一步查找后一子数组。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子数组不存在为止，此时查找不成功。

时间复杂度

时间复杂度即是while循环的次数。

总共有n个元素，

渐渐跟下去就是n,n/2,n/4,….n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数

由于你n/2^k取整后>=1

即令n/2^k=1

可得k=log2n,（是以2为底，n的对数）

所以时间复杂度可以表示O(h)=O(log2n)

题目

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例：

1 2	输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true

题解

这里提供一个自认为的最优解

若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。

代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int low = 0;
        int high = m * n - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = matrix[mid / n][mid % n];
            if (midVal < target) {
                low = mid + 1;
            } else if (midVal > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}