// Author : Khadiza Sultana
// Date : 1/4/2025
#include <iostream>
#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    int st = 0, end = nums.size() - 1;
    while (st <= end) {
        int mid = st + (end - st) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[st] <= nums[mid]) { // Left half is sorted
            if (nums[st] <= target && target <= nums[mid]) {
                end = mid - 1;
            } else {
                st = mid + 1;
            }
        } else { // Right half is sorted
            if (nums[mid] <= target && target <= nums[end]) {
                st = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;

    int result = search(nums, target);

    if (result != -1) {
        cout << "Target " << target << " found at index: " << result << endl;
    } else {
        cout << "Target " << target << " not found in the array." << endl;
    }

    return 0;
}

// Author : Khadiza Sultana
// Date : 1/4/2025
#include<iostream>
#include<vector>
using namespace std;

int binarySearch(vector<int>&arr, int tar) { // practical implementation
    int n = arr.size();
    int st = 0, end = n-1;
    while(st <= end) {
        int mid = st + (end-st)/2; // not using (st+end)/2 to avoid integer overflow
        if (tar > arr[mid]) {
            st = mid+1;
        }
        else if (tar < arr[mid]) {
            end = mid-1;
        }
        else {
            return mid;
        }
    }
    return -1;
}

int binarySearch2(vector<int>&arr, int tar, int st, int end) { // recursive implementation
    if (st > end) { // base case
        return -1;
    }
    int mid = st + (end-st)/2;
    if (tar > arr[mid]) {
        binarySearch2(arr, tar, mid+1, end);
    }
    else if (tar < arr[mid]) {
        binarySearch2(arr, tar, st, mid-1);
    }
    else {
        return mid;
    }
}

int main() {
    vector<int>arr1 = {3, 5, 7, 12, 15, 18}; // even no of elements
    int tar1 = 3;
    vector<int>arr2 = {4, 6, 10, 11, 12, 18, 19}; // odd no of elements
    int tar2 = 19;

    cout << "Index at which tar1 is found(even no of elements) : " << binarySearch(arr1, tar1) << endl;
    cout << "Index at which tar2 is found(odd no of elements) : " << binarySearch(arr2, tar2) << endl;
    
    cout << "Using Recusive function index at which tar1 is found : " << binarySearch2(arr1, tar1, 0, 5) << endl;
    cout << "Using Recusive function index at which tar1 is found : " << binarySearch2(arr2, tar2, 0, 6) << endl;

    return 0;
}

// Author : Khadiza Sultana
#include<iostream>
#include<vector>
using namespace std;

int main() {
    int a = 10;
    int* ptr = &a;
    int** parPtr = &ptr;
    cout << ptr << endl;
    cout << parPtr << endl;
    cout << *(&a) << endl;
    cout << *(ptr) << endl;
    cout << *(parPtr) << endl;
    cout << **(parPtr) << endl;
    return 0;
}

// Author : Khadiza Sultana
#include<iostream>
#include<vector>
using namespace std;
int LinearSearch(vector<int> &vec, int target){
    int i = 0;
    for(int val : vec){
        if(val == target)
           return i;
        i++;
    }
    return -1;
}
int main(){
    vector<int> vec = {1, 2, 5, 8, 5, 7, 8};
    int target = 7;
    cout << LinearSearch(vec, target) << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
    // Vector of integers
    std::vector<int> vecObj {11, 12, 13, 14, 15, 16, 12, 43, 12, 13, 11};

    // Sort the values in vector
    std::sort(vecObj.begin(), vecObj.end());

    // Remove duplicate values from vector
    vecObj.erase(std::unique(vecObj.begin(), vecObj.end()), vecObj.end());

    // print all elements of vector
    for(auto elem : vecObj) {
        std::cout<<elem << ", ";
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

string IntToString(int arr[], int k){
	string ans;

	for(int i = 0;i<k;i++){
		ans+= to_string(arr[i]);
	}
	return ans;
}

void StringToInt(string s){
	vector<int>v;
	map<int, int> mp;
	for(int i = 0;i<s.length();i++){
		v.push_back(s[i]-'0');
	}
	sort(v.begin(), v.end());
	for(int i = 0;i<v.size();i++){
		mp[v[i]]++;
	}
	cout<<"counting the frequency : \n";
	for(auto i:mp){
			cout<<i.first<<" "<<i.second<<endl;
	}
}

int main(){
	string s = "123343233434435";
	int brr[] = {2,3,4,5,6,7};
	int n = sizeof(brr)/sizeof(brr[0]);
	cout<<IntToString(brr, n)<<endl;
	StringToInt(s);
	return 0;
}