Last active
July 27, 2023 03:55
-
-
Save WizzyGeek/1758a1feb6ec48f5ad8c7ba79d7cf086 to your computer and use it in GitHub Desktop.
Array stuff
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment