Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jonathan-nwosu/27b9e42029fbc0d626397646a3e855fd to your computer and use it in GitHub Desktop.
Save jonathan-nwosu/27b9e42029fbc0d626397646a3e855fd to your computer and use it in GitHub Desktop.
Finding the number of occurrences of an integer in a sorted array using binary search
//
// main.cpp
// interview_questions
//
// Created by Jonathan Nwosu on 25/03/2017.
// Copyright © 2017 Jonathan Nwosu. All rights reserved.
//
#include <stdio.h>
#include <iostream>
using namespace std;
int binaryOccurance(int array[], int size, int x, bool searchFirst){
int low, high, result, mid;
low = 0;
high = size - 1;
result = -1;
while (low <= high){
mid = (low+high)/2;
if(array[mid] == x){
result = mid;
if(searchFirst)
high = mid -1; //Go on searching towards the left (lower indices)
else
low = mid +1; // Go on searching towards the right (higher indices)
}
else if(x < array[mid]) high = mid -1;
else low = mid+1 ;
}
return result;
}
int main() {
int array[] = {1,1,3,3,5,5,5,5,5,9,9,11};
int size = sizeof(array)/sizeof(array[0]);
int x;
cout << "Number to find in array: " << endl;
cin >> x;
//cout << "Appears: ";
//cout << findCount(array, size, x) << "times."<< endl;
int firstIndex = binaryOccurance(array, size, x, true);
if(firstIndex == -1){
printf( "Count of %d is %d",x,0);
} else {
int lastIndex = binaryOccurance(array, size, x, false);
printf("Count of %d is %d",x,lastIndex - firstIndex + 1);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment