Help with binary search

I need create a binary search that computes and prints the average search cost.

This is what I have so far..the last part is my sortList. If it is incorrect please help :P

Thanks

Code:

#include <stdio.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define MAXNAMESIZE 32
#define MAXLISTSIZE 1000
#define TEST TRUE

int readList(char[][MAXNAMESIZE]);
void printList(char[][MAXNAMESIZE], int);
void testSequentialSearch(char[][MAXNAMESIZE], int);
void writeList(char[][MAXNAMESIZE], int);
int sequentialSearch(char[][MAXNAMESIZE], int, char[]);



int main() {
	
	
	int listSize;
	char nameList[MAXLISTSIZE][MAXNAMESIZE];
	
	listSize = readList(nameList); 
	if (TEST) printList(nameList, listSize);
	testSequentialSearch(nameList, listSize);
	if (TEST) printList(nameList, listSize);
	writeList(nameList, listSize);

	return 0;
}

int readList(char nameList[][MAXNAMESIZE]) {

	FILE *fp;
	int length, listSize = 0;
	char name[MAXNAMESIZE];

	fp = fopen("names.txt", "r"); 

	while (fgets(name, MAXNAMESIZE, fp) != NULL) { 
		length = strlen(name);
		if (name[length-1]=='\n') name[length-1] = '\0';

		if (strlen(name)>0) {
			strcpy(nameList[listSize],name);
			listSize = listSize + 1;
		}
	}

	fclose(fp);

	return listSize;
}

void printList(char nameList[][MAXNAMESIZE], int listSize) {

		int i;
		
		if (listSize == 0) {
			printf("Empty list\n");
			return;
		} else {
			for (i=0; i<listSize; i++) {
				printf("&#37;s\n",nameList[i]);
			}
		}

		return;
}

void testSequentialSearch(char nameList[][MAXNAMESIZE], int listSize) {
	
	int i, searchCost = 0;
	float aveSearchCost; 

	for (i=0; i<listSize; i++) {
		searchCost = searchCost + sequentialSearch(nameList, listSize, nameList[i]);
	}
	
	if (searchCost == 0) aveSearchCost = 0;
	else aveSearchCost = (float) searchCost/ (float) listSize;

	printf("Average cost of sequential search = %f\n",aveSearchCost);
	return;
}

int sequentialSearch(char nameList[][MAXNAMESIZE], int listSize, char targetValue[]) {

	int i, cost = 0;

	if (listSize == 0) {
		printf("Search failed.\n");
	} else {
		for (i=0; i<listSize; i++) {
			cost = cost + 1;
			if (strcmp(nameList[i], targetValue)==0) {
				return cost;
			}
		}
		printf("Search failed.\n");
	}

	return cost;
}

void writeList(char nameList[][MAXNAMESIZE], int listSize) {

	FILE *fp;
	int i = 0;

	fp = fopen("sortedNames.txt","w");

	for (i=0; i<listSize; i++) {
		fprintf(fp,"%s\n",nameList[i]);
	}

	fclose(fp);

	return;
}

void insertionSort(int numbers[], int array_size)
{
  int i, j, index;

  for (i=1; i < array_size; i++)
  {
    index = numbers[i];
    j = i;
    while ((j > 0) && (numbers[j-1] > index))
    {
      numbers[j] = numbers[j-1];
      j = j - 1;
    }
    numbers[j] = index;
  }
}

Write a small program that tests your sort function. Once you get it working, add it do your main program.


Quzah.

Okay thanks.

Okay. So I'm having some trouble. What kind of code should I have?

One that attempts to do a binary search?
http://cboard.cprogramming.com/annou...t.php?f=4&a=39

If you search Google or Wikipedia with "binary search", as well as perhaps looking in a textbook(?) you've at least got a starting point.

well I totally suck at programming. I just started a few days ago. It confuses the hell out of me. It would really be appreciated if I could get some code =\

is this for a class? i dont think an intro programming class would be doing something like this 'a few days' into it.

if your very confused, i dont think theres any point in trying to attempt this at this stage. start doing basic programs, perhaps following the tutorials on this website.

tutorials:
http://www.cprogramming.com/tutorial.html

heres a useful link if you want the answer. if you want to learn, i suggest doing what i mentioned above. http://cprogramming.com/discussionar...searching.html

It's for a concepts in computer science class. csc-2001. not really sure why he's having us do it..half the class is lost.

well he definetly has valid reason to teach it in that class. however i dont think it should be taught in C, if this is an intro/first programming course.

if youre a CS major, it would be very wise to look at many of the tutorials, and write your own binary search. you dont need to know syntax or any programming language.. just draw boxes on a piece of paper and think how you would search through it, using english or common sense. (its easy once youve done it many times, however may seem difficult to come up with or understand your first few times).

the 'binary' in 'binary search' means that for each iteration of the search, your spliting the list in half. when the search is first called, you look at the middle element of a list. you then decide whether to look to elements greater than the middle one or less than (which would mean you search the list again, but only the 1st or 2nd half of it). you repeat this until you find the element your looking for.

right. we've gone through how the process works..i just don't know how to code it =\

call me dumb i guess but i'll try to figure it out. thanks for the help.

so if i copy the code that's on that link it'll will give me what i need? lol i feel like a complete tool asking for help on this. i've done python and other languages but this is my first time working with C

i think a big thing new programmers have difficulty with is that they dont think! by this i mean they just look at all the weird syntax and foreign language of programming and are overwhelmed.

ive said this to others before, think about it like your teaching a young child how to search through a list. the thing about computers is that they know nothing--they have to be told exactly what to do, when to do it, and how to do it.

another (very important) thing to note is that for a binary search to work, the list must be sorted, and you must know the length of the list.

lets say i have this list:

Code:

1   2   3   4   5

this list is sorted. its length is 5. how would come up with a way of telling the computer to find the number '4'? honestly.. get a piece of paper and try and think about it. the first hint is that you start by looking at the element at index (length / 2). when you find a solution, use another list, say '1 2 3' and see if it works again. your solution has to work in every posible case.

search wikipedia for a description of binary search or elsewhere.

edit:

so if i copy the code that's on that link it'll will give me what i need?

i dont know, will it?

It's just like the old kids game of "guess the number". (This was before video games came along.)

Basically, you're just cutting the search space in half, on each incorrect guess.

Wikipedia should tell you all about it.

Adak

Originally Posted by nadroj

edit:
i dont know, will it?

Good question...I don't know and I don't even know how to test it lol

as mentioned above, just try and work it out using the above methods, or search wikipedia page, or wherever you want for how or why it works. or, again, better yet try and think of it yourself!