# Find count of a number in sorted array

• Int sorted array, with repeated numbers.
Given a number K, return the count of K in the array
e.g. 3, 5, 5, 5, 5, 7, 8, 8
k = 6 return ->0
k = 5 return ->4

• Use findLeft and findRight to get the left and right edge index of K, then
the length of K is right - left + 1

``````static int  findLeft(int[] A, int key) {
int len = A.length;
int b = 0;
int e = len - 1;

while (b <= e) {
int mid = b + (e-b)/2;

if (A[mid] == key) {
if (mid - 1 <= 0 || A[mid-1] < key) {
System.out.println(">>> left " + mid);
return mid;
} else {
e = mid - 1;
}
} else if (A[mid] < key) {
b = mid + 1;
} else { // A[mid] > key
e = mid - 1;
}
}

return -1;
}

static int  findRight(int[] A, int key) {
int len = A.length;
int b = 0;
int e = len - 1;

while (b <= e) {
int mid = b + (e-b)/2;

if (A[mid] == key) {
if (mid + 1 >= len || A[mid+1] > key) {
System.out.println(">>> right " + mid);
return mid;
} else {
b = mid + 1;
}
} else if (A[mid] < key) {
b = mid + 1;
} else { // A[mid] > key
e = mid - 1;
}
}

return -1;
}
``````

• ``````int divide_search(int *data, int len, int target)
{
int mid, count, index;

if (len <= 0)
return 0;

if (len == 1)
{
if (data[0] == target)
return 1;
else
return 0;
}

mid = len / 2 - 1;

if (data[mid] == target)
{
//count
count = 1;
index = mid-1;
while ((index >= 0) & (data[index] == target))
{
count++;
index--;
}

index = mid+1;
while((index < len) && (data[index] == target))
{
count++;
index++;
}
return count;
}
else if (data[mid] > target)
{
return divide_search(data, mid-1, target);
}
else
{
return divide_search(&data[mid+1], len-mid-1, target);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.