为什么右移操作会stack overflow?

J
  • 3
新手上路,请多包涵

剑指offer上的一道题目,找到排序数组中k出现的次数

//采用二分查找找到第一个k和最后一个k的位置
public class Solution {
    public int getNumberOfK(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int firstK = getFirstK(nums, 0, nums.length - 1, k);
        int lastK = getLastK(nums, 0, nums.length - 1, k);
        int res = -1;
        if (firstK != -1 && lastK != -1) {
            res = lastK - firstK + 1;
        }
        return res;

    }

    private int getFirstK(int[] nums, int start, int end, int k) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end) / 2;
        // 不知为什么这样为stack overflow
        //int mid = (start + end) >> 2;
        if (nums[mid] > k) {
            return getFirstK(nums, start, mid - 1, k);
        } else if (nums[mid] < k) {
            return getFirstK(nums, mid + 1, end, k);
        } else {
            if (mid == 0 || nums[mid - 1] != k) { //k的前一个数不是k
                return mid;
            } else {
                return getFirstK(nums, start, mid - 1, k);
            }
        }

    }

    private int getLastK(int[] nums, int start, int end, int k) {
        if (start > end) {
            return -1;
        }
        int mid = (start + end) / 2;
        if (nums[mid] > k) {
            return getLastK(nums, start, mid - 1, k);
        } else if (nums[mid] < k) {
            return getLastK(nums, mid + 1, end, k);
        } else {
            if (mid == nums.length - 1 || nums[mid + 1] != k) {//k的后一个数不是k
                return mid;
            } else {
                return getLastK(nums, mid + 1, end, k);
            }
        }
    }
}

回复
阅读 195
1 个回答
✓ 已被采纳

/2操作的话,右移一位就可以了,你这样相当于是/4操作,另外这样的算法也不是很严谨,可以选择使用(end-start)/2 + start,防止出现数组过大导致的int值溢出问题

你知道吗?

宣传栏