CODEWITHSUNDEEP
javaarraysalgorithmsearchcomplexity-theory
Zvi vex
Zvi vex

Reputation: 53

Count the number of appearances of a value in a sorted array in O(log n) complexity

How can I build a function that returns the number of appearances of a given int x in a sorted array, in O(log n) complexity?

static public int count (int [] a, int x);

I'm thinking I might use a binary search to the find the first / last appearance, then continue searching for the last / first appearance, and return the number of instances, but that this is O(log n) complexity .

Upvotes: 3

Views: 523

Answers (2)

HopefullyHelpful
HopefullyHelpful

Reputation: 1799

Here my solution. In a sorted array binarySearch finds the position of a number in log(n) steps. If the number is not present it finds the position that the number should be at, if it were in the array. If you search for x+-1/2 those values will never be in the array, but instead will give you the bounds for x, because it tries to find a value lower/higher than x that cannot exist in an integer array. The comparison automatically converts your ints to double so that everything runs flawlessly.

import java.util.ArrayList;
import java.util.List;

public class SearchCount {
    public static void main(String[] args) {
        final List<Integer> test = new ArrayList<Integer>();
        for(int i = 1; i <= 100; i++) {
            for(int j = 0; j < i && i != 50; j++) {
                test.add(i);
            }
        }
        final int[] intTest = new int[test.size()];
        for (int j = 0; j < test.size(); j++) {
            final int i = test.get(j);
            intTest[j] = i;
        }
        for(int x = 0; x <= 101; x++) {
            System.out.println(count(intTest,x));
        }
    }
    public static int count (int[] a, int realKey) {
       final double lowKey = realKey-0.5;
       final double highKey = realKey+0.5;
       final int lowerBound = binarySearch(a,0,a.length-1,lowKey);
       final int upperBound = binarySearch(a,0,a.length-1,highKey);
       return upperBound-lowerBound;
    }

   public static int binarySearch(int[] data, int low, int high, double key)
   {
        while(high >= low) {
            final int middle = (low + high) / 2;
            if(data[middle] < key) {
                low = middle + 1;
            }
            if(key < data[middle]) {
                high = middle - 1;
            }
      }
      return high < low?low:high;
   }
}

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 372942

Your idea actually works in time O(log n) if you implement it correctly. Do one binary search to find the index i of the first copy of the element, then do another binary search to find the index j of the last copy of the element, then return j - i + 1. Each binary search takes time O(log n), so the total work done is O(log n) + O(log n) = O(log n).

Upvotes: 3

Related Questions