binary search, count duplicates
<p>I have sorted array</p>

<pre><code>{1,2,3,5,5,5,7,8,8}
</code></pre>

<p>I would like to count how many times the number that i am sending is found in the array in longn only.</p>

<p>for example:</p>

<pre><code>public static int count(int[] array,5)
</code></pre>

<p>will reply 3</p>

<pre><code>public static int count(int[] array,8)
</code></pre>

<p>will reply 2</p>

<p>so my plan is:</p>

<p>1) to do a binary search to find the number</p>

<p>2) binary search the top border index and the bottom border index.</p>

<p>3) print (top index - bottom index) will give me the time of target number in the array.</p>

<p>Is my code is logn ?
Please help! :)</p>

<pre><code>    public class binarySearch
{
    public static void main(String[]args)
    {
        System.out.println("d");
        int[]data={1,1,2,3,1,1,1};
        System.out.println(count(data,1));
    }

    public static int count(int[] a, int x)
    {
        int low=0;
        int high = a.length-1;
        int count=0;

        while(low &lt;=high)
        {
            int mid=((low+high)/2);         
            if(x&gt;a[mid])
                low=mid+1;
            if(x&lt;a[mid])
                high=mid-1;

            if(x==a[mid])            
            {
                int top=findTopIndex(a,x,mid);                
                int bottom=findBottomIndex(a,x,mid);
                return (top-bottom);

            }

        }    
        return 111111111;

    }

    public static int findTopIndex(int[] a, int x, int index)
    {
        int low=index;
        int high = a.length-1;    
        int mid;
        if(x==a[high])
        return high;

        while(low &lt;= high)
        {            
           mid=((low+high)/2);         
           if(x&lt;a[mid]&amp;&amp;x==a[mid-1])
           return mid-1;
           else if(x==a[mid])
                low=mid+1;
           else if(a[mid]&gt;x &amp;&amp; a[mid-1]!=x)
           high=mid-1;


        } 
        return 11111111;

    }
    public static int findBottomIndex(int[] a, int x, int index)
    {
        int low=0;
        int high = index-1;    
        int mid;
        if(x==a[low])
        return low-1;

        while(low &lt;= high)
        {            
         mid=((low+high)/2);         
           if(x&gt;a[mid]&amp;&amp;x==a[mid+1])
           return mid;
           else if(x==a[mid])
                high=mid-1;
           else if(a[mid]&lt;x &amp;&amp; a[mid+1]!=x)
           low=mid+1;

        } 
        return 111;

    }

}
</code></pre>
