Binary Search

Search Element using Binary search in the Linear & 2-D Arrays

Time Complexity always O(Logn)

Q1: Binary Search

int BinarySearch(int arr[], int key, int size){
    int s = 0; // starting index
    int e = size-1; // ending index 
    while(s <= e){
        int mid = s + (e - s)/2;
        if(arr[mid] == key){
            return mid;
        }

        // if arr[mid] != key, then decide the part using this conditions > or <
        else if(arr[mid] > key){
            e = mid - 1;
        }
        else{
            s = mid + 1;
        }
    }
    return -1;
} 

Q2: First and Last Occurrence of K-element in a Sorted Array

int FirstOccu(vector <int> arr, int k, int n){
    int s = 0, e = n-1;
    int ans = -1;
    while (s <= e){
        int mid = s + (e-s)/2;
        if(arr[mid] == k){
            ans = mid;
            e = mid - 1;
        }
        else if(arr[mid] < k){
            s = mid + 1;
        }
        else if(arr[mid] > k){
            e = mid - 1;
        }
    }
    return ans;
}
int LastOccu(vector <int> arr, int k, int n){
    int s = 0, e = n-1;
    int ans = -1;
    while (s <= e)
    {
        int mid = s + (e-s)/2;
        if(arr[mid] == k){
            ans = mid;
            s = mid + 1;
        }
        else if(arr[mid] < mid){
            s = mid + 1;
        }
        else if(arr[mid] > mid){
            e = mid - 1;
        }
    }
    return ans;
}

int main(){
    vector <int> arr = {1,4,4,4,4,5};
    int First =  FirstOccu(arr, 4, 6);
    int Last =  LastOccu(arr, 4, 6);
    cout << "First Occurence of 3: " <<First << endl;
    cout << "Last Occurence of 3: " << Last << endl;
    
    // Condition for finding the total occurrences of an element
    int total = (Last - First) + 1;
    cout<<"Total of 3 present in array: " << total << endl;
}

Q3: Peak Index in a Mountain Array

int peakIndexInMountainArray(vector<int>& arr) {
    int s = 0;
    int e = arr.size() - 1;
    while(s <= e){ 
        int mid = s+(e-s)/2; 
        if(arr[mid] < arr[mid+1]) 
            s = mid + 1; 
        else 
            e = mid - 1; 
    }
    return s; 
}

Q4: Pivot Index

#include <iostream>
using namespace std;

int findMinimum(int *arr, int n) {
    int s = 0;
    int e = n-1;
    
    while (s<=e) {
        int mid = s+(e-s)/2;
        if(arr[mid] >= arr[0])  s = mid+1;
        else e = mid-1;
    }
    return arr[s];
}

int main() {
    int arr[] = {4,5,6,7,0,1,2};
    int n = sizeof(arr)/sizeof(int);
    cout << findMinimum(arr, n);
}

Q5: Search in Rotated-Sorted Array

int search(vector<int>& arr, int k) {
    int Pivot = GetPivot(arr);
    int n = arr.size() - 1;
    if(arr[Pivot] <= k && k <= arr[n]){
        return BinarySearch(arr, Pivot, n, k);
    }
    else{
        return BinarySearch(arr, 0, Pivot - 1, k);
    }
}

int GetPivot(vector<int>& arr){
    int s = 0;
    int e = arr.size() - 1;
    while (s < e){
        int mid = s+(e-s)/2;
        if(arr[mid] >= arr[0]){
            s = mid + 1;
        }
        else{
            e = mid;
        }
    }
    return s;
}

int BinarySearch(vector<int>& arr, int start, int end, int k){
    int s = start;
    int e = end;
    while (s <= e){
        int mid = s + (e - s) / 2;
        if(arr[mid] == k){
            return mid;
        }
        else if(arr[mid] < k){
            s = mid + 1;
        }
        else{
            e = mid - 1;
        }
    }
    return -1;
}

Q6: sqrt(x)

long long int SqrtInteger(int n){
    int s = 0;
    int e = n;
    long long int ans = -1;
    long long int square;
    while (s<=e){
        long long int mid = s+(e-s)/2;
        square = mid*mid;
        if(square == n){
            return mid;
        }
        else if(square < n){
            ans = mid;
            s = mid + 1;
        }
        else{
            e = mid - 1;
        }
    }
    return ans; 
}
// extra 
double morePricision(int n, int pricision, int tempSol){
    double factor = 1;
    double ans = tempSol;
    for (double i = 0; i < pricision; i++){
        factor /= 10;
        for (double j = ans; j*j < n; j += factor){
            ans = j;
        }
    }
    return ans;
}
int main(){
    int n = 37;
    int temp = SqrtInteger(n);
    cout << morePricision(n, 4, temp);
}

Q7: Search a 2D Matrix-I

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    
    int row = matrix.size();
    int col = matrix[0].size();
    
    int s = 0;
    int e = (row*col)-1;

    while(s <= e){
        int mid = s + (e - s) / 2;
        int element = matrix[mid/col][mid%col];
        if(element == target){
            return true;
        }
        else if(element < target){
            s = mid + 1;
        }
        else{
            e = mid - 1;
        }
    }
    return false;
}


T.C = O(logn) // n = row*col
T.C = O(log(row*col))

Q8: Search a 2D Matrix-II

bool searchMatrix(vector<vector<int>>& matrix, int target) {
       int row = matrix.size();
       int col = matrix[0].size();

       int startingRow = 0;
       int endingCol = col-1;
       while(startingRow < row && endingCol >= 0) {
            int element = matrix[startingRow][endingCol];
            if(element == target) {
                return true;
            }
            else if(element > target) {
                endingCol--;
            }
            else{
                startingRow++;
            }
       }
       return false;
    }