zad3

mail@pastecode.io avatar
unknown
csharp
a year ago
1.4 kB
0
Indexable
Never
public static uint binary_search(uint[] arr, ulong searched) {

        /*
        Worst-case performance = O(log n)
        Best-case performance = O(1)
        Average performance = O(log n)
        Worst-case space complexity = O(1)
        */

        int min_num = 0, max_num = arr.Length - 1;
		uint ops = 0;

        while (min_num <= max_num) {
            
            int mid = (min_num + max_num) / 2;
            ulong long_mid = Convert.ToUInt64(arr[mid]);
            if (searched == long_mid) {
                ops++;
                return ops;
            } else if (searched < long_mid) {
                ops++;
                max_num = mid - 1;
            } else {
                ops++;
                min_num = mid + 1;
            }
        }
        return ops;
    }

    public static uint linear_search(uint[] arr, ulong searched) {

        /*
        Worst-case performance = O(n)
        Best-case performance = O(1)
        Average performance = O(n)
        Worst-case space complexity = O(1) iterative
        */

        int size = arr.Length;
		uint ops = 0;

        for (int i = 0; i < size; i++) {
            ulong curr = Convert.ToUInt64(arr[i]);
            ops++;
            if (curr == searched){
                return ops;
            }
        }
        return ops;
    }