搜索算法题目是笔试面试中常考的一类题目。

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 比较：

1. 当 leftDown < target，由于 m 已经是该行最大的元素，想要更大只有从列考虑，取值右移一位 
2. 当 leftDown > target，由于 m 已经是该列最小的元素，想要更小只有从行考虑，取值上移一位 
3. 当 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;
    }