# Binary Search

Can we improve the algorithm?

``````#include <iostream>
using std::cout;
using std::endl;

int binarySearch(int array[], int x, int low, int high) {

if (high >= low) {
int mid = low + (high - low) / 2;

// Case 1: if x == A[mid]
if (x == array[mid])
{
return mid;
}
// Case 2: x < A[mid]
if (x < array[mid])
{
return binarySearch(array, x, low, mid - 1);
}
// x > A[mid]
return binarySearch(array, x, mid + 1, high);
}

return -1;
}

int main(void) {
int array[] = {2, 6, 13, 36, 47, 63, 81, 97};
int x = 13;
int n = sizeof(array) / sizeof(array);
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
else
cout << "Element is found at index: " << result << endl;
}
``````

Output:

``````Element is found at index: 2
``````

Time Complexity

Best Case Average Case Worst Case
O(1) O(log n) O(log n)

Space Complexity

O(1)

### Finding the first or last Occurrence of a Number

``````#include <iostream>
using std::cout;
using std::endl;

// Function for finding first and last occurrence of an elemtn

void FindFirstAndLast(int A[], int n, int x)
{
int first = -1, last = -1;
for (int i = 0; i < n; i++) {
if (x != A[i])
continue;
if (first == -1)
first = i;
last = i;
}
// print results
if (first != -1)
cout << "First Occurrence = " << first
<< "\nLast Occurrence = " << last;
else
}

// Driver code
int main()
{
int A[] = { 2, 4, 10, 10, 10, 18, 20, 25, 40};
int n = sizeof(A) / sizeof(int);
int x = 10;

cout << "Finding the first and last occurence of: " << x << endl;
FindFirstAndLast(A, n, x);
cout << endl;

}
``````

Output:

``````Finding the first and last occurence of: 10
First Occurrence = 2
Last Occurrence = 4
``````
``````#include <iostream>
using std::cout;
using std::endl;

#include<string>
using std::string;

int CountOccurrences(int arr[], int n, int x)
{
int occurence = 0;
for (int i=0; i<n; i++)
if (x == arr[i])
occurence++;
return occurence;
}

int main()
{
int arr[] = {1, 1, 3, 3, 5, 5, 5, 5, 5, 9, 9, 11};
int n = sizeof(arr)/sizeof(arr);
int x = 5;

int occur = CountOccurrences(arr, n, x);
cout << "The Number of Occurrences of " << x << " is: " << occur << endl;
}
``````

Output:

``````The Number of Occurrences of 5 is: 5
``````

Time Complexity

Worst Case: O(n)

### How many Times is a Sorted Array Rotated?

• Common Interview Question
• Simply just find the index of the min value
``````#include <iostream>
using std::cout;
using std::endl;

int countRotations(int arr[], int n)
{
// Simply just find the index of the min value
int min = arr, min_index;
for (int i=0; i<n; i++)
{
if (min > arr[i])
{
min = arr[i];
min_index = i;
}
}
return min_index;
}

int main()
{
int A[] = {11,15,20,45,1,2,3,4,5,6,7,8,9,10};
int n = sizeof(A)/sizeof(A);

int count = countRotations(A, n);
cout << "The array is rotated " << count << " times!" << endl;
}
``````
``````The array is rotated 4 times!
``````