程序员必备小知识：一文带你攻克搜索算法题目
1.二维数组中的查找
描述
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
数据范围：矩阵的长宽满足 0≤n,m≤5000，矩阵中的值满足 0≤val≤10^9
进阶：空间复杂度 O(1) ，时间复杂度 O(n+m)
示例1
输入：
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]] 复制代码
返回值：
true 复制代码
说明：
存在7，返回true 复制代码
示例2
输入：
1,[[2]] 复制代码
返回值：
false 复制代码
示例3
输入：
3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]] 复制代码
返回值：
false 复制代码
说明：
不存在3，返回false 复制代码
题解1
暴力二分搜索：
针对于n行，每一行采用二分查找去寻找target，某一行找到直接返回true，如果都找不到，则返回false；
时间复杂度:O(n*logm)
空间复杂度:O(1)
public class Solution { public boolean Find(int target, int [][] array) { if(array.length == 0){ return false; } for(int[] arr : array){ if(arr.length == 0){ return false; } if(arr[0] <= target){ boolean ans = binarySearch(target,arr); if(ans == true){ return true; } } } return false; } public boolean binarySearch(int target, int[] arr){ int left = 0; int right = arr.length - 1; while(left <= right){ int mid = left + (right-left)/2; if(arr[mid] > target){ right = mid - 1; }else if(arr[mid] < target){ left = mid+1; }else{ return true; } } return false; } } 复制代码题解2 从左下角搜索（右上角搜索也是同理）
利用该二维数组的性质：
每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序
改变个说法，即对于左下角的值 leftDown，leftDown是该行最小的数，是该列最大的数
每次将 leftDown 和目标值 target 比较：
当 leftDown < target，由于 m 已经是该行最大的元素，想要更大只有从列考虑，取值右移一位
当 leftDown > target，由于 m 已经是该列最小的元素，想要更小只有从行考虑，取值上移一位
当 leftDown = target，找到该值，返回 true
用某行最小或某列最大与 target 比较，每次可剔除一整行或一整列
public class Solution { public boolean Find(int target, int [][] array) { int rows = array.length; if(rows == 0){ return false; } int cols = array[0].length; if(cols == 0){ return false; } int i = rows-1; int j = 0; while(i>=0 && j<=cols-1){ int leftDown = array[i][j]; // 左下角的值 if(leftDown > target){ i -= 1; }else if(leftDown < target){ j += 1; }else{ return true; } } return false; } } 复制代码总结
题解二主要是由于本题矩阵的特殊性，今后做题某步遇到搜索某值，可以像题解1一样用二分查找，复杂度O(logn)<线性查找O(n)。
2.旋转数组的最小数字
描述
有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤100000
要求：空间复杂度：O(1)，时间复杂度：O(logn)
示例1
输入：
[3,4,5,1,2] 复制代码
返回值：
1 复制代码
示例2
输入：
[3,100,200,3] 复制代码
返回值：
3 复制代码
题解
主要采用二分法，分以下几个情况：
[1,2,3,4,5] 依次递增，输出1
[3,4,5,1,2] 第一轮：low=0，high=4，mid=2指向5，5>2，low指针应右移至mid+1=3，指向1。第二轮，low=3，high=4，mid=3指向1，此时array[low=3] < array[high=4]，令high=mid=3。第三轮，low=high，return array[low]=1。
[2,0,2,2,2] 第一轮：low=0，high=4，mid=2指向2，注意，这里特殊在array[mid]=array[high]=array[low]，所以你就无法判断最小值究竟是在mid左还是右，我们做了一个low++ 的处理去缩小范围。第二轮，low=1，high=4，mid=2，此时注意，array[low]<array[high]，所以直接return0。
import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { int low = 0; int high = array.length - 1; while(low < high){ if(array[low] < array[high]){ // [1,2,3,4,5] 这种特殊情况 return array[low]; } int mid = low + (high - low)/2; if(array[mid] > array[high]){ low = mid + 1; }else if (array[mid] < array[high]){ high = mid; }else{ low++; } } return array[low]; } } 复制代码结束总结
基础的二分法模板如下，很多题都是在此基础上做得改动。
public boolean binarySearch(int target, int[] arr){ int left = 0; int right = arr.length - 1; while(left <= right){ int mid = left + (right-left)/2; if(arr[mid] > target){ right = mid - 1; }else if(arr[mid] < target){ left = mid+1; }else{ return true; } } return false; }
作者：conghuhu
链接：https://juejin.cn/post/7019987346086952996