Searching Flashcards
Binary Search and implementation of the iterative algorithm.
#include (iostream> using namespace std;
int bSearch(int arr[], int n, int x)
{
int low = 0, high = n - 1;
while(low (= high)
{
int mid = (low + high) / 2;
if(arr[mid] == x)
return mid;
else if(arr[mid] > x) high = mid - 1;
else low = mid + 1; } return -1; }
int main() {
int arr[] = {10, 20, 30, 40, 50, 60}, n = 6;
int x = 25;
cout((bSearch(arr, n, x);
return 0; }
Recursive binary search implementation
#include (iostream> using namespace std;
int bSearch(int arr[], int low, int high, int x)
{
if(low > high)
return -1;
int mid = (low + high) / 2; if(arr[mid] == x) return mid;
else if(arr[mid] > x) return bSearch(arr, low, mid - 1, x);
else return bSearch(arr, mid + 1, high, x); }
int main() {
int arr[] = {10, 20, 30, 40, 50, 60, 70}, n = 7;
int x = 20;
cout((bSearch(arr, 0, n - 1, x);
return 0; }
What is ternary search and how it is implemented?
Let me explain ternary search and provide a Java implementation.
public class TernarySearch {
/**
* Performs ternary search on a sorted array to find target element.
* Returns index of the target if found, -1 otherwise.
* Time Complexity: O(log3 n)
*/
public static int ternarySearch(int[] arr, int target) {
return ternarySearchRecursive(arr, target, 0, arr.length - 1);
}
private static int ternarySearchRecursive(int[] arr, int target, int left, int right) {
if (right < left) {
return -1;
}
// Find the two mid points that divide array into three parts
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
// Check if target is at either mid point
if (arr[mid1] == target) {
return mid1;
}
if (arr[mid2] == target) {
return mid2;
}
// Decide which third to search in
if (target < arr[mid1]) {
// Search in first third
return ternarySearchRecursive(arr, target, left, mid1 - 1);
} else if (target > arr[mid2]) {
// Search in last third
return ternarySearchRecursive(arr, target, mid2 + 1, right);
} else {
// Search in middle third
return ternarySearchRecursive(arr, target, mid1 + 1, mid2 - 1);
}
}
// Example usage
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int target = 5;
int result = ternarySearch(arr, target);
if (result != -1) {
System.out.println("Element " + target + " found at index " + result);
} else {
System.out.println("Element " + target + " not found");
}
}
}
Ternary search is a divide-and-conquer algorithm similar to binary search, but instead of dividing the array into two parts, it divides it into three roughly equal parts. Here’s how it works:
- The algorithm divides the sorted array into three parts using two midpoints (mid1 and mid2)
- It compares the target value with the elements at both midpoints
- Based on these comparisons, it determines which third of the array to search next
- This process continues recursively until the element is found or the search space is empty
The time complexity is O(log₃ n), which is slightly worse than binary search’s O(log₂ n). While ternary search makes fewer comparisons per iteration, it requires more comparisons at each step (2 instead of 1), making it generally less efficient than binary search in practice.
The main advantage of ternary search comes when searching for a maximum or minimum in a unimodal function, where it can be more efficient than binary search.
List three C++ STL functions for binary search?
Some of these functions are:
binary_search()
upper_bound()
lower_bound()
What is binary_search?
This function only checks if a particular element is present in a sorted container or not. It accepts the starting iterator, ending iterator and the element to be checked as parameters and returns True if the element is present otherwise False.
// C++ code to demonstrate the working // of binary_search()
#include(bits/stdc++.h> using namespace std;
int main()
{
/*** USING binary_search() ON VECTOR ***/
// initializing vector of integers
vector(int> vec = {10, 15, 20, 25, 30, 35};
// using binary_search to check if 15 exists
if (binary_search(vec.begin(), vec.end(), 15))
cout (( "15 exists in vector";
else
cout (( "15 does not exist";
cout (( endl;
/*** USING binary_search() ON ARRAYS ***/
int arr[] = {10, 15, 20, 25, 30, 35};
int n = sizeof(arr)/sizeof(arr[0]);
// using binary_search to check if 20 exists
if (binary_search(arr, arr + n, 20))
cout (( "20 exists in Array";
else
cout (( "20 does not exist";
return 0; }
What is upper_bound?
The upper_bound() function is used to find the upper bound of an element present in a container. That is it finds the location of an element just greater than a given element in a container. This function accepts the start iterator, end iterator and the element to be checked as parameters and returns the iterator pointing to the element just greater than the element passed as the parameter. If there does not exist any such element than the function returns an iterator pointing to the last element.
// CPP program to illustrate using upper_bound() // with vectors and arrays
#include (bits/stdc++.h> using namespace std;
// Driver code
int main()
{
/*** USING upper_bound() WITH VECTOR ***/
vector(int> v{ 10, 20, 30, 40, 50 };
// Print vector
cout (( "Vector contains :";
for (int i = 0; i ( v.size(); i++)
cout (( " " (( v[i];
cout (( "\n";
vector(int>::iterator upper1, upper2;
// std :: upper_bound
upper1 = upper_bound(v.begin(), v.end(), 35);
upper2 = upper_bound(v.begin(), v.end(), 45);
cout (( "\nUpper_bound for element 35 is at position : "
(( (upper1 - v.begin());
cout (( "\nUpper_bound for element 45 is at position : "
(( (upper2 - v.begin())(("\n\n";
/*** USING upper_bound() WITH ARRAY ***/
int arr[] = { 10, 20, 30, 40, 50 };
// Print elements of array
cout (( "Array contains :";
for (int i = 0; i ( 5; i++)
cout (( " " (( arr[i];
cout (( "\n";
// using upper_bound
int up1 = upper_bound(arr, arr+5, 35) - arr;
int up2 = upper_bound(arr, arr+5, 45) - arr;
cout (( "\nupper_bound for element 35 is at position : "
(( (up1);
cout (( "\nupper_bound for element 45 is at position : "
(( (up2);
return 0; }
What is lower_bound?
The lower_bound() function is used to find the lower bound of an element present in a container. That is it finds the location of an element just smaller than a given element in a container. This function accepts the start iterator, end iterator and the element to be checked as parameters and returns the iterator pointing to the lower bound of the element passed as the parameter. If all elements of the container are smaller are less than the element passed, then it returns the last iterator.
// CPP program to illustrate lower_bound() // for both vectors and array
#include (bits/stdc++.h> using namespace std;
// Driver code
int main()
{
/*** USING lower_bound() ON VECTORS ***/
vector(int> v{ 10, 20, 30, 40, 50 };
// Print vector
cout (( "Vector contains :";
for (int i = 0; i ( v.size(); i++)
cout (( " " (( v[i];
cout (( "\n";
vector(int>::iterator low1, low2;
// using lower_bound()
low1 = lower_bound(v.begin(), v.end(), 20);
low2 = lower_bound(v.begin(), v.end(), 55);
cout (( "\nlower_bound for element 20 at position : "
(( (low1 - v.begin());
cout (( "\nlower_bound for element 55 at position : "
(( (low2 - v.begin());
/*** USING lower_bound() ON ARRAYS ***/
int arr[] = { 10, 20, 30, 40, 50 };
// Print elements of array
cout (( "\n\nArray contains :";
for (int i = 0; i ( 5; i++)
cout (( " " (( arr[i];
cout (( "\n";
// using lower_bound()
int lb1 = lower_bound(arr, arr + 5, 20) - arr;
int lb2 = lower_bound(arr, arr + 5, 55) - arr;
cout (( "\nlower_bound for element 20 is at position : "
(( (lb1);
cout (( "\nlower_bound for element 55 is at position : "
(( (lb2);
return 0; }
Given an unsorted array of size n. Array elements are in the range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in the array. Find these two numbers.
Examples:
Input: arr[] = {3, 1, 3}
Output: Missing = 2, Repeating = 3
Explanation: In the array,
2 is missing and 3 occurs twice
Input: arr[] = {4, 3, 6, 2, 1, 1}
Output: Missing = 5, Repeating = 1
Method 1 (Use Sorting) Approach:
Sort the input array.
Traverse the array and check for missing and repeating.
Time Complexity: O(nLogn)
Thanks to LoneShadow for suggesting this method.
Method 2 (Use count array) Approach:
Create a temp array temp[] of size n with all initial values as 0.
Traverse the input array arr[], and do following for each arr[i]
if(temp[arr[i]] == 0) temp[arr[i]] = 1;
if(temp[arr[i]] == 1) output “arr[i]” //repeating
Traverse temp[] and output the array element having value as 0 (This is the missing element)
Time Complexity: O(n)
Auxiliary Space: O(n)
Method 3 (Use elements as Index and mark the visited places)
Approach:
Traverse the array. While traversing, use the absolute value of every element as an index and make the value at this index as negative to mark it visited. If something is already marked negative then this is the repeating element. To find missing, traverse the array again and look for a positive value.
// C++ program to Find the repeating
// and missing elements
#include using namespace std;
void printTwoElements(int arr[], int size)
{
int i;
cout << " The repeating element is ";
for (i = 0; i < size; i++) {
if (arr[abs(arr[i]) - 1] > 0)
arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
else
cout << abs(arr[i]) << "\n";
}
cout << "and the missing element is ";
for (i = 0; i < size; i++) {
if (arr[i] > 0)
cout << (i + 1);
}
}
/* Driver code */
int main()
{
int arr[] = { 7, 3, 4, 5, 5, 6, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
printTwoElements(arr, n);
}
Output
The repeating element is 5
and the missing element is 1
Time Complexity: O(n)
Method 6 (Use a Map) Approach: This method involves creating a Hashtable with the help of Map. In this, the elements are mapped to their natural index. In this process, if an element is mapped twice, then it is the repeating element. And if an element’s mapping is not there, then it is the missing element.
Below is the implementation of the above approach: // C++ program to find the repeating // and missing elements using Maps #include #include using namespace std;
int main()
{
int arr[] = { 4, 3, 6, 2, 1, 1 };
int n = 6;
unordered_map numberMap;
for(int i : arr)
{
if (numberMap.find(i) ==
numberMap.end())
{
numberMap[i] = true;
}
else
{
cout << "Repeating = " << i;
}
}
cout << endl;
for(int i = 1; i <= n; i++)
{
if (numberMap.find(i) ==
numberMap.end())
{
cout << "Missing = " << i;
}
}
return 0;
}
Count number of occurrences using binary search
// C++ program to count occurrences of an element // in a sorted array. # include (bits/stdc++.h> using namespace std;
/* if x is present in arr[] then returns the count
of occurrences of x, otherwise returns 0. */
int count(int arr[], int x, int n)
{
/* get the index of first occurrence of x */
int *low = lower_bound(arr, arr+n, x);
// If element is not present, return 0 if (low == (arr + n) || *low != x) return 0;
/* Else get the index of last occurrence of x.
Note that we are only looking in the
subarray after first occurrence */
int *high = upper_bound(low, arr+n, x);
/* return count */ return high - low; }
/* driver program to test above functions */
int main()
{
int arr[] = {1, 2, 2, 3, 3, 3, 3};
int x = 3; // Element to be counted in arr[]
int n = sizeof(arr)/sizeof(arr[0]);
int c = count(arr, x, n);
printf(" %d occurs %d times ", x, c);
return 0;
}
Given a binary sorted non-increasing array of 1s and 0s. You need to print the count of 1s in the binary array.
Example 1:
Input:
N = 8
arr[] = {1,1,1,1,1,0,0,0}
Output: 5
Explanation: Number of 1's in given
binary array : 1 1 1 1 1 0 0 0 is 5.
Example 2:
Input:
N = 8
arr[] = {1,1,0,0,0,0,0,0}
Output: 2
Explanation: Number of 1's in given
binary array : 1 1 0 0 0 0 0 0 is 2.
Your Task:
The task is to complete the function countOne() which takes the array arr[] and its size N as inputs and returns the count of 1s in the input array.
Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(1).
Constraint:
1 <= N <= 5*106
arr[i] = 0,1
int low = 0, high = N - 1;
int mid = high - (high - low) / 2;
// binary search to count 1s
while (low (= high) {
mid = high - (high - low) / 2;
// check if mid is 1
if (arr[mid] == 1 && mid + 1 ( N && arr[mid + 1] == 1) {
low = mid + 1;
}
// if mid is not 0, then iterate for lower half
else if (arr[mid] == 0) {
high = mid - 1;
}
// else iterate for upper half
else if (arr[mid] == 1 && ((mid + 1 ( N && arr[mid + 1] == 0) || (mid == N - 1))) {
return mid + 1;
}
}
return 0;
find square root of a number
long long int floorSqrt(long long int x)
{
//base case
if (x == 0 || x == 1)
return x;
long long int start = 1, end = x, ans;
// binary search to find square root of a number
while (start (= end)
{
long long mid = (start + end) / 2;
// check if mid*mid == x
if (mid*mid == x)
return mid;
// if mid*mid ( x, then iterate on the upper half
if (mid*mid ( x)
{
start = mid + 1;
ans = mid;
}
// else, iterate for the lower half
else
end = mid - 1;
}
return ans;
}
Majority element
METHOD 3 (Using Moore’s Voting Algorithm):
Approach: This is a two-step process.
The first step gives the element that maybe the majority element in the array. If there is a majority element in an array, then this step will definitely return majority element, otherwise, it will return candidate for majority element.
Check if the element obtained from the above step is majority element. This step is necessary as there might be no majority element.
Algorithm:
Loop through each element and maintains a count of majority element, and a majority index, maj_index
If the next element is same then increment the count if the next element is not same then decrement the count.
if the count reaches 0 then changes the maj_index to the current element and set the count again to 1.
Now again traverse through the array and find the count of majority element found.
If the count is greater than half the size of the array, print the element
Else print that there is no majority element
Below is the implementation of above idea // C++ Program for finding out // majority element in an array #include (bits/stdc++.h> using namespace std;
/* Function to find the candidate for Majority */
int findCandidate(int a[], int size)
{
int maj_index = 0, count = 1;
for (int i = 1; i ( size; i++) {
if (a[maj_index] == a[i])
count++;
else
count--;
if (count == 0) {
maj_index = i;
count = 1;
}
}
return a[maj_index];
}
/* Function to check if the candidate
occurs more than n/2 times */
bool isMajority(int a[], int size, int cand)
{
int count = 0;
for (int i = 0; i ( size; i++)
if (a[i] == cand)
count++;
if (count > size / 2)
return 1;
else
return 0; }
/* Function to print Majority Element */
void printMajority(int a[], int size)
{
/* Find the candidate for Majority*/
int cand = findCandidate(a, size);
/* Print the candidate if it is Majority*/
if (isMajority(a, size, cand))
cout (( " " (( cand (( " ";
else
cout (( "No Majority Element"; }
/* Driver code */
int main()
{
int a[] = { 1, 3, 3, 1, 2 };
int size = (sizeof(a)) / sizeof(a[0]);
// Function calling
printMajority(a, size);
return 0; }
