程序员必备小知识：一文带你攻克搜索算法题目
搜索算法题目是笔试面试中常考的一类题目。
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];
}
}
3.数字在升序数组中出现的次数
描述
给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数。
数据范围：0≤n≤1000,0≤k≤1000≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100。 要求：空间复杂度 O(1)，时间复杂度O(logn)。
示例1
输入：
[1,2,3,3,3,3,4,5],3
复制
返回值：
4
示例2
输入：
[1,3,4,5],6
返回值：
0
题解1 二分法查找
先二分查找k第一次出现的下标，再二分查出k第二次出现的下标，然后作差+1，为k的数量。
时间复杂度：O(logn) 空间复杂度：O(1)
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int first = firstIndex(array,k);
int last = lastIndex(array,k);
if(first == -1 || last == -1){
return 0;
}
return last - first + 1;
}
public int firstIndex(int [] array, int k) {
int low = 0;
int high = array.length-1;
while(low <= high){
if(array[low] == array[high] && array[low] == k){
return low;
}
if(low == high && array[low] == k){
return low;
}
int mid = low + (high - low)/2;
if(array[mid] > k){
high = mid-1;
}else if(array[mid] < k){
low = mid+1;
}else{
high = mid;
}
}
return -1;
}
public int lastIndex(int [] array, int k) {
int low = 0;
int high = array.length-1;
while(low <= high){
if(array[low] == array[high] && array[low] == k){
return high;
}
if(low == high && array[high] == k){
return high;
}
int mid = low + (high - low)/2;
if(array[mid] > k){
high = mid-1;
}else if(array[mid] < k){
low = mid+1;
}else{
low = mid;
}
}
return -1;
}
}
题解二：基于题解一的优化
先用二分查找随便找到一个k的下标，然后向前和向后搜索。 这里二分查找直接调的Arrays类自带的函数。
public static int binarySearch(Object[] a, Object key)
用二分查找算法在给定数组中搜索给定值的对象(Byte,Int,double等)。数组在调用前必须排序好的。
如果查找值包含在数组中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。
时间复杂度：O(logn) 空间复杂度：O(1)
import java.util.Arrays;
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int index = Arrays.binarySearch(array,k);
if(index < 0){
return 0;
}
int count = 1;
for(int i = index -1; i >= 0; i--){
if(array[i] == k){
count++;
}else{
break;
}
}
for(int i = index+1; i < array.length; i++){
if(array[i] == k){
count++;
}else{
break;
}
}
return count;
}
}
结束总结
基础的二分法模板如下，很多题都是在此基础上做得改动。
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;
}