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

38 数字在排序数组中出现的次数(改正了二分查找的等于号)

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

题目描述
统计一个数字在排序数组中出现的次数。
第一种方法:遍历一遍数组,统计一下.
第二种:二分查找

public class Solution {
    public int minBinarySearch(int[] array,int k){
        int low = 0,high = array.length - 1;
        while(low <= high){
            int mid = (low + high) / 2;
            if(array[mid] > k){
                high = mid - 1;
            }else if(array[mid] < k)
                low = mid + 1;
            else{
                //如果下标大于0,并且前一位的值也是k
                if((mid >0) && (array[mid-1]==k))
                    high = mid - 1;
                else
                    return mid;
            }
        }
        return -1;
    }
    public int maxBinarySearch(int[] array,int k){
        int low = 0,high = array.length - 1;
        while(low <= high){
            int mid = (low + high) / 2;
            if(array[mid] > k){
                high = mid - 1;
            }else if(array[mid] < k)
                low = mid + 1;
            else{
                if((mid < array.length-1) && (array[mid+1]==k))
                    low = mid + 1;
                else
                    return mid;
            }
        }
        return -1;
    }
    public int GetNumberOfK(int [] array , int k) {
        int i = minBinarySearch(array,k);
        int j = maxBinarySearch(array,k);
        if(i == -1 || j == -1)
            return 0;
       return j-i+1;
    }
}

注意:while(low <= high)中一定要有等于号的!!!
eg:【1,2,3,3,3,3,4,5】
判断第一个3的时候:mid = 3,这时候令high= mid-1 = 2;low = 0,所以mid = 1,=》令low = 2,此时:low == high,但是无法进行比较了,出错!

我之前的《二分法小晋级》里面的想法是错的,while里面什么时候是小于等于号,什么时候是小于号,现在还不清楚!循环里面的判断靠的是mid前面的数字是否和现在的相同,以及mid之后的数字是否和现在的相同来判断的!

补充:二分查找按理来说肯定得是等号,因为它必须得判断那一位。其实究竟是什么符号还是得看情景。没有什么固定的规律,不过这里可以加等号。
最原始的二分查找也应该是while(i <= j)的。可以从递归的角度来看。

并思考了快排的不等号。
参考:https://www.cnblogs.com/edisonchou/p/4822740.html