欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer-37-数字在排序数组中出现的次数(二分查找) -- Java实现

程序员文章站 2024-03-20 12:03:40
...

题目

统计一个数字在排序数组中出现的次数。

分析

思路一:

代码:

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int low = 0;
        int high = array.length - 1;
        int mid = low + (high - low) / 2;
        int numK = 0;
        while(low <= high) {
            mid = low + (high - low) / 2;
            if(array[mid] == k) {
                numK++;
                int midR = mid + 1;
                int midL = mid - 1;
                while(midR <= array.length - 1 && array[midR] == k) {
                    numK++;
                    midR++;
                }
                while(midL >= 0 && array[midL] == k) {
                    numK++;
                    midL--;
                }
                return numK;
            } else if(array[mid] > k) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        return numK;
    }
}
相关标签: 算法与数据结构