Tuesday lecture code

#include <stdio.h>
#include <stdlib.h>

int linearSearch(int a[],int n,int key);

int main(void){
	int size;
	int key;
	int i;
	printf("Enter number of elements:");
	scanf("%d",&size);
//printf("Enter key to search for:");
//scanf("%d",&key);
	key = -99;
	int * a = malloc(size * sizeof(int));
	printf("Enter elements:\n");
	for(i=0;i<size;i++){
		scanf("%d",&a[i]);
	}

	int result = linearSearch(a,size,key);
	if(result != -1){
		printf ("Found at index %d\n",result);
	}else{
		printf ("Did not find element %d\n",key);
	}
	return 0;
}

int linearSearch(int a[],int n,int key){
	int i;
	for(i=0;i<n;i++){
		if(key == a[i]){
			printf("%d %d\n",key,a[i]);
			return i;   //return the index
		}
	}
	return -1;        //return -1 if not found
}

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

ssize_t binary_search (int a[], size_t n, int key);
static bool prompt_int (char *, int *);

int main (void)
{
	int size;
	prompt_int ("Enter number of elements: ", &size);

	int key;
	// prompt_int ("Enter key to search for: ", &key);
	key = -99;

	int *a = calloc (size, sizeof(int));
	puts ("Enter elements...");

	for (size_t i = 0; i < (unsigned int)size; i++)
		scanf ("%d",&a[i]);

	printf ("binary_search(%d) ... ", key);
	ssize_t result = binary_search(a,size,key);
	if (result != -1)
		printf ("found at index %zu\n", result);
	else
		printf ("not found\n");

	return EXIT_SUCCESS;
}

static bool prompt_int (char *prompt, int *n)
{
	fputs (prompt, stdout);
	return scanf ("%d", n) == 1;
}

//         { 1, 2, 3, 4, 5, 6, 8, 9, 10 } (n = 9)
//                          ^ == 7
// step 3:              lo |  | hi
// step 2:                 | lo      hi |
// step 1: | lo                      hi |
//
// Binary search takes log2(n) steps ... n = 9 => log2(9) ~= 3

ssize_t binary_search (int a[], size_t n, int key)
{
	size_t lo = 0, hi = n - 1;
	while (hi >= lo) {
		size_t mid = (lo + hi) / 2;
		if (a[mid] == key) return mid;
		if (a[mid]  > key) hi = mid - 1;
		if (a[mid] <  key) lo = mid + 1;
	}
	return -1;
}

#include <err.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <sysexits.h>

typedef uint64_t u64;

u64 good_fib (u64 n);

int main (int argc, char *argv[])
{
	if (argc != 2)
		errx (EX_USAGE, "usage: bad_fib <num>");

	long n = strtol (argv[1], NULL, 10);

	printf ("fib(%ld) = %" PRIu64 "\n", n, good_fib (n));

	return EXIT_SUCCESS;
}

// Code to return the nth fibonacci number
// 0 1 1 2 3 5 8 13 etc
//
// This version caches intermediate results, an approach known as
// "dynamic programming", leading to increased efficiency.
u64 good_fib (u64 n)
{
	u64 tmp;
	u64 prev1 = 0;
	u64 prev2 = 1;
	for (u64 i = 0; i < n; i++) {
		tmp = prev1;
		prev1 = prev2;
		prev2 = tmp + prev2;
	}
	return prev1;
}

#include <err.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <sysexits.h>

typedef uint64_t u64;

u64 bad_fib (u64 n);

int main (int argc, char *argv[])
{
	if (argc != 2)
		errx (EX_USAGE, "usage: bad_fib <num>");

	long n = strtol (argv[1], NULL, 10);

	printf ("fib(%ld) = %" PRIu64 "\n", n, bad_fib (n));

	return EXIT_SUCCESS;
}

// Code to return the n'th fibonacci number
// 0 1 1 2 3 5 8 13 etc
//
// This code is very inefficient! It is exponential.
// Time it with input of say 30 vs 45 vs 46 vs 47 etc
u64 bad_fib (u64 n)
{
	switch (n) {
	case 0:  return 0;
	case 1:  return 1;
	default: return bad_fib (n-1) + bad_fib (n-2);
	}
}