sorted search function c++ code example

Example 1: binary_search in vector in c++

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//defining the comparator function returns true or false
//not for binary search..
bool f(int x, int y){
	return x>y; //for decreasing order
}
	
int main() {
	
	vector<int> A ={ 11,2,3,14 };
	cout<<A[1]<<endl;//2
  
	sort(A.begin(), A.end()); // sort in order to perform binary search
	cout<<A[1]<<endl;//3 after sorting
	
	bool present = binary_search(A.begin(), A.end(), 3);
	cout<<present<<endl;//will return true
  
	present = binary_search(A.begin(), A.end(), 5);
	cout<<present<<endl;//will return false
  
	A.push_back(100);//inserting new element from end
  
	present = binary_search(A.begin(), A.end(), 100);
	cout<<present<<endl;
  
   	A.push_back(100);
	A.push_back(100);
	A.push_back(100);
	A.push_back(121);
	
	//give me the iterator pointing to first element >= 100
	vector<int>::iterator it = lower_bound(A.begin(), A.end(), 100);
	//you can also use auto as c++ will see that a lower_bound is performed
	//and it will figur it out that it is an iterator of vector<int>
	//auto it = lower_bound(A.begin(), A.end(), 100);
	//auto it2 = upper_bound(A.begin(), A.end(), 100);
	
	
	
	//give me an iterator pointing to first element >100
	vector<int>::iterator it2 = upper_bound(A.begin(), A.end(), 100);
	
	//print the content of it and it2
	cout<<*it<<" "<<*it2<<endl;
	
	//give me the number of hundreds(100)
	cout<<it2-it<<endl; //4 it subtracts the indices 
	
	
	//soritng the vector in reverse order
	//use method overloading with sort by passing a comparator function 
	//to control the ordering
	sort(A.begin(), A.end(), f);
	
	//now print the sorted vector using iterator
	vector<int>::iterator it3;
	
	for (it3 =A.begin(); it3!= A.end(); it3++){
		cout<<*it3<<" ";
	}
	cout<<endl;
	
	//A shorter code for the above will be
	for(int x: A){
		//x++ wont change the vector content it will only print the changed one
		cout<<x<<" ";
	}
	cout<<endl;
	
	//to change the vector content while iterating
	//iterate it by referance by using &x
	for(int &x: A){
		x++;
		cout<<x<<" ";
	}
	cout<<endl;
  
	return 0;
}

Example 2: dichotomic search c++

using namespace std; 
  
// A recursive binary search function. It returns 
// location of x in given array arr[l..r] is present, 
// otherwise -1 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 
  
int main(void) 
{ 
    int arr[] = { 2, 3, 4, 10, 40 }; 
    int x = 10; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int result = binarySearch(arr, 0, n - 1, x); 
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result; 
    return 0; 
}