Binary Search
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[0]);
int result = binarySearch(array, x, 0, n - 1);
if (result == -1)
cout << "Not Found! " << endl;
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
cout << "Not Found";
}
// 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
Count Occurences of a number in a sorted array with duplicates using Binary Search
#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[0]);
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[0], 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[0]);
int count = countRotations(A, n);
cout << "The array is rotated " << count << " times!" << endl;
}
The array is rotated 4 times!