剑指 Offer 53 - I. 在排序数组中查找数字 I

class Solution {
    public int search(int[] nums, int target) {
        int number =0;
        if(nums != null && nums.length>0){
            int first = getFirstK(nums,nums.length,target,0,nums.length-1);
            int last = getLastK(nums,nums.length,target,0,nums.length-1);
        
            if(first >-1 && last >-1){
                number = last -first +1;
            }
        }
        return number;
    }
    int getFirstK(int[] data,int length,int k,int start,int end){
        if(start>end){
            return -1;
        }
        int midIndex = (start + end)/2;
        int midData = data[midIndex];

        if(midData == k){
            if((midIndex > 0 && data[midIndex-1] != k) || midIndex == 0 ){
                return midIndex;
            }else {
                end = midIndex -1 ;
            }

        }else if (midData >k){
            end = midIndex-1;
        }else{
            start = midIndex +1 ;
        }
        return getFirstK(data,length,k,start,end);
        
    }
    int getLastK(int[] data,int length,int k,int start,int end){
        if(start > end){
            return -1;
        }
        int midIndex = (start + end)/2;
        int midData = data[midIndex];

        if(midData == k){
            if((midIndex < length-1 && data[midIndex+1]!= k)|| midIndex == length-1){
                return midIndex;
            }else{
                start = midIndex +1;
            }
        } else if(midData > k){
            end = midIndex -1 ;
        }else{
            start = midIndex +1 ;
        }
        return getLastK(data,length,k,start,end);
    }
}

LeetCode上大佬解法 ,干净,简洁

剑指 Offer 53 - I. 在排序数组中查找数字 I

 

上一篇:旋转数组的最小数字【记录】


下一篇:【二叉树】【打卡69天】《剑指Offer》2刷:JZ33 二叉搜索树的后序遍历序列