二维数组中的查找
题目要求
本题有三种常规思路:
1、就是最普通的遍历二维数组,这种思路适合于二维数组较小的情况,
时间复杂度:?。
2、把每一行看成有序递增的数组,利用二分查找,
通过遍历每一行得到答案,
时间复杂度:nlogn。
上面两个二分查找,虽然类似,但是,把int mid=(low+high)/2;
语句放置的位置不同,造成的性能差异很大哟,有兴趣的读者可以尝试一下。
3、利用二维数组由上到下,由左到右递增的规律,那么选取右上角或者左下的元素a[row][col]与target进行比较,当target小于元素a[row][col]时,那么target必定在元素a所在行的左边,即col–;
当target大于元素a[row][col]时,那么target必定在元素a所在列的下边,即row++;
时间复杂度:?
注意:因while循环中条件&是短路运算符,所以两个语句前后顺序变了就会造成数组越界。