【题 53】在排序数组中查找数字

缺乏、安全感 2022-03-02 06:36 132阅读 0赞

【题目】  
统计一个数字在排序数组中出现的次数。  
【思路】  
用二分查找找到第一个k和最后一个k。  
【实现】

public class Solution {
        public int GetNumberOfK(int [] array , int k) {
           int length = array.length;
            if(length == 0){
                return -1;
            }
            int firstK = getFirstK(array,k,0,length-1);
            int lastK = getLastK(array,k,0,length-1);
            if(firstK != -1&&lastK != -1){
                return lastK -firstK+1;
            }
            return 0;
        }
        
        //递归写法
        private int getFirstK(int[] array,int k,int start,int end){
            if(start>end){
                return -1;
            }
            int mid = (start+end)>>1;
        }
        if(array[mid] >k){
            return getFirstK(array,k,start,mid-1);
        }else if(array[mid]<k){
            return getFirstK(array,k,mid+1,end);
        }else if(mid-1>=0&&array[mid-1]==k){
            return getFirstK(array,k,start,mid-1);
        }else{
            return mid;
        }
        
        //循环写法
        private int getLastK(int[] array,int k,int start,int end){
            int length = array.length;
            int mid = (start + end)>>1;
            while(start <= end){
                if(array[mid]>k){
                    end = mid-1;
                }else if(array[mid]<k){
                    start = mid+1;
                }else if(mid+1 <length &&array[mid+1]==k){
                    start = mid+1;
                }else{
                    return mid;
                }
                mid = (start+end)>>1;
            }
            return -1;
        }
    }

参考：  
1.《剑指offer》  
2.[https://www.nowcoder.com/profile/835689/codeBookDetail?submissionId=1522853][https_www.nowcoder.com_profile_835689_codeBookDetail_submissionId_1522853]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]

[https_www.nowcoder.com_profile_835689_codeBookDetail_submissionId_1522853]: https://www.nowcoder.com/profile/835689/codeBookDetail?submissionId=1522853
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220302/0dba8952ddc64412b68db1461c923408.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220302/e918de2b79f74c4dbea15562e340f4db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]: /images/20220302/25b0ad9cf5a84e5f8b02ecc10e650e0b.png