1_查找.md

查找

1、二维数组中的查找（1）

二维数组中的查找

public boolean Find(int target, int [][] array) {
    if(array==null || array.length==0){
        return false;
    }
    int m = array.length;
    int n = array[0].length;

    //从该二维数组的右上角 (0,n-1) 位置开始查找
    //类似二分查找
    for(int i=0,j=n-1;i<m && j>=0;){
        if(array[i][j]==target){
            return true;
        }else if(array[i][j]<target){ //(array[i][j] 值小了，向下移动值才会变大
            i++;
        }else{
            assert array[i][j]>target;
            j--;
        }
    }
    return false;
}

2、旋转数组的最小数字（21）

旋转数组的最小数字

//思路一：
public int minNumberInRotateArray(int [] array) {
    if(array==null || array.length==0){
        return 0;
    }
    if(array.length==1){
        return array[0];
    }
    //此时数组中至少有 2 个元素
    int res = array[0];
    for(int i=1;i<array.length;i++){
        if(array[i-1]>array[i]){
            res = array[i];
            break;
        }
    }
    return res;
}

//思路二：
//利用二分查找的思想
//关键在于确定旋转数组在那一部分
// 当 nums[m] <= nums[h] 时，表示 [m, h] 区间内的数组是非递减数组，
// 则 [l, m] 区间内的数组是旋转数组，此时令 h = m；
// 否则 [m + 1, h] 区间内的数组是旋转数组，令 l = m + 1。
public int minNumberInRotateArray(int [] array) {
    if(array==null || array.length==0){
        return 0;
    }
    if(array.length==1){
        return array[0];
    }

    int l=0;
    int h=array.length-1;
    while(l<h){
        int m = (h-l)/2+l;
        if(array[m]<=array[h]){ //[l,m] 是旋转数组
            h = m;
        }else{ //[m+1,h] 是旋转数组
            l =m+1;
        }
    }
    return array[l];
}

3、数字在排序数组中出现的次数（52）

数字在排序数组中出现的次数

//写法一：
//[l,r] 闭区间中进行查找

public int GetNumberOfK(int [] array , int k) {
    int first = binarySearchFirst(array,k); //获取第一个出现 k 元素的下标
    int last = binarySearchLast(array,k);//获取最后一个出现 k 元素的下标
    if(first==-1){ //不存在 k，那就返回 0
        return 0;
    }
    return (last-first)+1;
}

//TODO：二分查找重复元素 k 出现的第一个下标
private int binarySearchFirst(int[] array,int k){
    int l=0;
    int r=array.length-1;
    int res=-1;
    while(l<=r){ //注意：循环的结束条件,这里是在[l,r] 闭区间中查找，允许 l==r
        int m = (r-l)/2+l;
        if(array[m]>=k){
            r=m-1;
        }else{
            l=m+1;
        }
        if(array[m]==k){
            res = m;
        }
    }
    return res;
}

//二分查找重复元素 k 出现的最后一个下标
private int binarySearchLast(int[] array,int k){
    int l=0;
    int r=array.length-1;
    int res=-1;
    while(l<=r){
        int m = (r-l)/2+l;
        if(array[m]<=k){
            l= m+1;
        }else{
            r=m-1;
        }
        if(array[m]==k){
            res = m;
        }
    }
    return res;
}

//写法二：
//[l,r） 左闭右开区间中进行查找
public int GetNumberOfK(int [] array , int k) {
    int first = binarySearchFirst(array,k); //获取第一个出现 k 元素的下标
    int last = binarySearchLast(array,k);
    if(first==-1){
        return 0;
    }
    return (last-first)+1;
}

//二分查找重复元素 k 出现的第一个下标
private int binarySearchFirst(int[] array,int k){
    int l=0;
    int r=array.length;
    int res=-1;
    while(l<r){
        int m = (r-l)/2+l;
        if(array[m]>=k){
            r=m;
        }else{
            l=m+1;
        }
        if(array[m]==k){
            res = m;
        }
    }
    return res;
}

//二分查找重复元素 k 出现的最后一个下标
private int binarySearchLast(int[] array,int k){
    int l=0;
    int r=array.length;
    int res=-1;
    while(l<r){
        int m = (r-l)/2+l;
        if(array[m]<=k){
            l= m+1;
        }else{
            r=m;
        }
        if(array[m]==k){
            res = m;
        }
    }
    return res;
}