search.c

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

int compare_int(void* va, void* vb){

	int* a = va; 
	int* b = vb;
	return *b - *a;

}

int compare_cstring (void* va, void* vb){
	char* a = *(char**)va;
	char* b = *(char**)vb;

	// return strcmp(a, b); I basically wrote an equivalent below

	while(*a != '\0' || *b != '\0'){
		if(*a != *b)
		{
			return -1;
		}
		a += sizeof(char);
		b += sizeof(char);
	};

	return 0;
}

void *lsearch(void *key, void *base, int n, int elemSize, int (*cmpfn)(void*, void*))
{
	int i;
	void *elemAddr = base;

	for(i=0; i<n; i++)
	{
		if(cmpfn(key,elemAddr) == 0){
			return elemAddr;
		}
		elemAddr = (char*)elemAddr + elemSize;
		
	}
	return NULL; /* nothing found*/
}

void *binary_search(void *key, void *base, int n, int elemSize, int (*cmpfn)(void*, void*))
{
	//binary search, finds the first occurence. Buggy!
	int i;
	void *left = base;
	void *right = base + n*elemSize;
	void *elemAddr = base + (n/2)*elemSize;

	void *found_equal = NULL;

	while(left < right){
		printf("%d %d\n", *(int*)key, *(int*)elemAddr);
		if(cmpfn(key,elemAddr) == 0)
		{
			found_equal = elemAddr;
			right = elemAddr;
			elemAddr = (char*)left + ((right-left)/2)*elemSize;
		}
		else if(cmpfn(key,elemAddr) > 0)
		{
			right = elemAddr;
			elemAddr = (char*)left + ((right-left)/2)*elemSize;
		}
		else
		{
			left = elemAddr;
			elemAddr = (char*)left + ((right-left)/2)*elemSize;
		}
	}

		// printf("%d\n", chunkSize);
		printf("%d %d\n", *(int*)key, *(int*)elemAddr);
	if(cmpfn(key,elemAddr) == 0)
	{
		return elemAddr;
	}
	else
	{
		return found_equal;
	}
}


int main(int argc, char const *argv[])
{
	int arr[] = {7,6,1,5,15,2,24,2,64,35,3};
	int arr_size = sizeof(arr)/sizeof(int);

	int key = 5;

	// printf("Please input an integer value to search: ");
	// scanf("%d", &key);

	int* found = lsearch(&key, arr, arr_size, sizeof(int), compare_int);

	printf("Array: %p\nFound: %p\nIndex: %ld\n", arr, found, found-arr);


	char* str_arr[] = {"abc", "h0i!", "temmie", "temshop"};
	int str_arr_size = sizeof(str_arr)/sizeof(char *);

	char* str_key = "temmie";

	// printf("Please input an string value to search: ");
	// scanf("%s", str_key);

	char** str_found = lsearch(&str_key, str_arr, str_arr_size, sizeof(char *), compare_cstring);

	printf("Array: %p\nFound: %p\nIndex: %ld\n", str_arr, str_found, str_found-str_arr);

	//sorted array
	// int sorted_arr[] = {1,1,4,7,9,14,23,35,65,84,91,100,121,143,167,198,200,201,255,255,365,400,404,405};
	int sorted_arr[] = {1,2,3,4,5};
	int sorted_arr_size = sizeof(sorted_arr)/sizeof(int);

	printf("Please input an integer value to search: ");
	scanf("%d", &key);

	found = binary_search(&key, sorted_arr, sorted_arr_size, sizeof(int), compare_int);

	printf("Array: %p\nFound: %p\nIndex: %ld\n", sorted_arr, found, found-sorted_arr);

	return 0;
}