binary_search.cpp

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

using namespace std;

#define N 30 // długość tablicy
#define NUM_TO_FIND 5
#define NUMBER_RANGE 20
#define LOG_DEBUG 1

int *prepareArray()
{
    srand(time(0));
    static int result[N];
    for (int i = 0; i < N; i++)
    {
        result[i] = rand() % NUMBER_RANGE;
    }
    sort(result, result + N);
    return result;
}

/**
 * Tutaj powinienem napisać dokumentację …
 *
 * @param *arr array to find index
 * @param num number to find
 * @return index of number to find in array, -1 if index not found
 */
int findIndex(int *arr, int num)
{
    int low = 0, high = N - 1; // ustawiamy wskaźniki na pierwszy i ostatni elem tablicy, nasz przedział wyszukiwania
    // No i tutaj sprawa złożoności jest bardziej skomplikowana bo nie masz pętli for którą iterujesz po tablicy
    // w zamian za to iterujesz do momentu w którym otrzymasz przedział jednoelementowy w tablicy ale zauważ że za każdym razem
    // dzieli pozostały przedział na 2 więc złożoność obliczeniową możemy oszacować jako O(log(N)) gdzie log to logarytm stopnia 2
    // złożoność pamięciowa to O(1) bo nie używamy dodatkowej pamięci
    if (LOG_DEBUG == 1) cout << "low: " << low << "; high: " << high << endl;
    
    while (low <= high)
    {
        int mid = low + (high - low) / 2;

        if (arr[mid] == num)
            return mid;
        if (arr[mid] < num)     // num większy od lewego przedziału
            low = mid + 1;      // zawężamy przedział z lewej strony
        else                    // num mniejszy od prawego przedziału
            high = mid - 1;     // zawężamy przedział z prawej strony
        
        // to poniżej żebyś mogła zobaczyć jak kod działa
        if (LOG_DEBUG == 1) cout << "low: " << low << "; mid: " << mid << "; high: " << high << endl;
    }
    return -1;
}

int main()
{
    int *arr = prepareArray();
    int idx = findIndex(arr, NUM_TO_FIND);
    for (int i = 0; i < N; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    cout << idx << endl;
}