Array stuff

array_ops.c

// Array operations
// Search
// Insert
// Traverse
// Update
#include<string.h>
#include<stdio.h>


// O(n) time
// O(1) space
void traverse(int *arr, int len, void foo(int)) {
    for (int i = 0; i < len; i++) {
        foo(arr[i]);
    }
}

// O(logn) time
// O(1) space
int bisect(int *arr, int len, int num) {
    int hi = len - 1;
    int lo = 0;

    int idx = lo + (hi - lo) / 2;

    while (1) {
        if (arr[idx] < num) {
            lo = idx + 1;
        }
        else if (arr[idx] > num) {
            hi = idx - 1;
        }
        else {
            return idx;
        }
        if (lo > hi) return -1;
        idx = lo + (hi - lo) / 2;
    }
}

// O(n) time
// O(1) space
int lin_search(int *arr, int len, int num) {
    if (len == 1) {
        return (arr[0] == num) - 1;
    }

    if (len < 1) { return -1; }

    len--;
    for (int i = 0; i <= (len + 1) / 2; i += 2) {
        if (arr[i] == num) return i;
        if (arr[i + 1] == num) return i + 1;
        if (arr[len - i - 1] == num) return len - i - 1;
        if (arr[len - i] == num) return len - i;
    }
    return -1;
}

// O(1) time
// O(1) space
int update_elem(int *arr, int len, unsigned int idx, int num) {
    if (idx < len) {
        arr[idx] = num;
        return 0;
    }
    else { return -1; }
}

// O(n - k) time where k is the insertion index
// O(1)
int insert(int *arr, int len, unsigned int idx, int num) {
    if (idx >= len) return -1;
    if ((len - idx - 1) == 0) {
        arr[idx] = num;
        return 1;
    }

    // This might be wrong, but it works on this machine
    memcpy(arr + idx + 1, arr + idx, sizeof(int) * (len - idx - 1));
    arr[idx] = num;
    return 0;
}

void printer(int num) {
    printf("%d ", num);
}

int main() {
    int arr[25];
    const int len = 25;

    for (int i = 0; i < len; i++) {
        insert(arr, len, i, i);
    }

    traverse(arr, len, printer);

    printf("\nBisect for 23: %d", bisect(arr, len, 23));
    printf("\nUpdate Returned: %d", update_elem(arr, len, 13, 999));
    printf("\nLinear Search for 999: %d\n", lin_search(arr, len, 999));
    // insert(arr, len, 0, 3);

    traverse(arr, len, printer);
}