Hello once again people; I hope I'm not breaking any rules or being cheeky. But I was searching for algorithms/programs on the internet that would help me with my binary search program, and then I came across the piece of code posted here (in the code snippets section)about just the type of searching I want to do - within an integer array. The page containing this code can be found here http://www.daniweb.com/code/snippet164.html.
So I ran this code, and it seemed to work alright... until I put in multiples of 5 and asked it to search for one of the numbers I put in. With this type of data (integers with steps of 5 between them), for some reason, it doesn't find some numbers. It's very erratic behaviour. Can anyone please tell me if I've done something wrong, or if the code is sort of meant to be like that?

I've included it below for anyone who's interested

// binary search of an integer array, this search is efficient for large arrays
// tested with PellesC vegaseat 24jan2005


#include <stdio.h>



int main(void)
{

int a[20] = {0};

int n, i, j, temp;

int *beg, *end, *mid, target;


printf(" enter the total integers you want to enter (make it less then 20):\n");

scanf("%d", &n);

if (n >= 20) return 0; // Ouch, too many!

printf(" enter the integer array elements:\n" );

for(i = 0; i < n; i++)

{

scanf("%d", &a[i]);

}


// sort the loaded array, a must for binary search!
// you can apply qsort or other algorithms here

for(i = 0; i < n-1; i++)

{

for(j = 0; j < n-i-1; j++)

{

if (a[j+1] < a[j])

{

temp = a[j];

a[j] = a[j+1];

a[j+1] = temp;

}

}

}

printf(" the sorted numbers are:");

for(i = 0; i < n; i++)

{

printf("%d ", a[i]);

}

// point to beginning and end of the array

beg = &a[0];

end = &a[n-1]; // use n = one element past the loaded array!

printf("\n beg points to address %d and end to %d",beg, end); // test

 

// mid should point somewhere in the middle of these addresses

mid = beg += n/2;

printf("\n mid points to address %d", mid); // test


printf("\n enter the number to be searched:");

scanf("%d",&target);


// binary search, there is an AND in the middle of while()!!!

while((beg <= end) && (*mid != target))

{

// is the target in lower or upper half?

if (target < *mid)

{
end = mid - 1; // new end

n = n/2;

mid = beg += n/2; // new middle
}

else

{
beg = mid + 1; // new beginning

n = n/2;

mid = beg += n/2; // new middle
}

}


// did you find the target?

if (*mid == target)
{
	printf("\n %d found!", target);
}

else
{
	printf("\n %d not found!", target);
}

getchar(); // trap enter
getchar(); // wait

return 0;

}

Apologies that the code is soo long...

binary search algorithms normally expect the elements to be unique and sorted in either ascending or descending order.

Comments about coding style:

It would be a lot better if you indented the code properly, such as indent sub-blocks of code that is enclosed in '{' and '}' braces by 4 or 5 spaces. For example, line 12 and all following lines should be indented 4 or 5 spaces to the right of line 10.

It isn't necessary to put a blank line between each line. Delete all those blank lines and it will make your program look a little more professional and easier to read.

Does your program perform the sorting properly? Try printing out the values of the array after sorting to see if it works. If yes then try putting print statements inside your Binary Search algorithm and see how the algorithm traverses through the array. And if it still doesn't work, post the code with proper formatting.

OK, I've indented the code, and put print statements in the Binary Search algorithm part of the code. The algorithm seems to recognise when a number is higher than or lower than the middle point, but it still doesn't find some numbers. I have been testing it with an array of 5 integers, and it only finds the middle and the last number in the array. So in an array containing 1,2, 3, 4, 5 if I search for all the numbers one after the other, the program finds only 3 and 5. Can anyone help out here please, I've checked the code with text books, and it appears to be right.

#include <stdio.h>
int a[5];

int main(void)
{
	int n, i, j, temp;
	int *beg, *end, *mid, target;
	int b, e, m;
	n = 5;
	
	printf("Please enter 5 integer array elements:\n" );

	for(i = 0; i < 5; i++)
	{
		scanf("%d", &a[i]);
	}


	/*The sorting is done here*/
	for(i = 0; i < n-1; i++)
	{
		for(j = 0; j < n-i-1; j++)
		{
			if (a[j+1] < a[j])
			{
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
	}

	printf("The sorted numbers are:");

	for(i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	
	// Point to 'beginning' and 'end' of the array

	beg = &a[0];
	end = &a[n-1]; // use n = one element past the loaded array!

	printf("\nVariable 'beg' points to address %d and 'end' points to %d", beg, end); // test

	// mid should point somewhere in the middle of these addresses

	mid = beg += n/2;

	printf("\n... And 'mid' points to address %d", mid); // test
	printf("\n Enter the number to be searched:");
	scanf("%d", &target);

	// This is the binary search
		
	while((beg <= end) && (*mid != target))
	{
		// Is the target in the lower or upper half?
		if (target < *mid)
		{
			printf("Target number is less than middle number\n");
			end = mid - 1; // new end
			printf("The value of 'end' is = %d\n", end);
			n = n/2;
			mid = beg += n/2; // new middle
			printf("The value of 'mid' is = %d\n", mid);
		}
		else
		{
			printf("Target number is more than middle number\n");
			beg = mid + 1; // new beginning
			printf("The value of 'beg' is = %d\n", beg);
			n = n/2;
			mid = beg += n/2; // new middle
			printf("The value of 'mid' is = %d\n", mid);
		}

	}


	// Was the target found?

	if (*mid == target)
	{
	printf("\n %d found!\n", target);
	}
	else
	{
	printf("\n %d not found!\n", target);
	}

	getchar(); // trap enter
	

	return 0;
}

Instead of using pointer variables for marking the beginning and the end, make your life simpler by keeping numbers as markers. That the calculations would become simpler and more logical. The bugs cropping up in your program are because of pointer calculation.

How about something simple like this?

Instead of using pointer variables for marking the beginning and the end, make your life simpler by keeping numbers as markers. That the calculations would become simpler and more logical. The bugs cropping up in your program are because of pointer calculation.

How about something simple like this?

Hi sos, thanks for the tip + link, I have incorporated both things into my program, and it seems to work, except that when I search for the 3rd item in the array, the program just terminates - it doesn't say either it found the number or it didn't even though I've got printf statements to handle both eventualities. I tried this for an array of 5 and 6 elements, and got the same thing.

The relevant section of the code is

// Assign variables to the beginning and end of the array

	b = 0;
	e = n-1;
	
	printf("This is the value of b: %d\n", b);
	printf("This is the value of e: %d\n", e);
	
	printf("\n Enter the number to be searched:");
	scanf("%d", &u);

	// This is the binary search
		
	while (b <= e)
	{
		m = (b + e) / 2;	/* Mid-point calculation*/
	
		if (u > a[m])
			b = m + 1;
		else if (u < a[m])
			e = m - 1;
		else
			return m;
			printf("Number %d has been found!\n", u);
	}
		
	return -(b + 1);
	printf("Sorry the number was not found. Goodbye!\n");

	return 0;

The rest of the code is pretty much as before. Hope someone can help cos I'm really stumped by this, I've tried altering the search statements to reflect something I saw in an ANSI C book by Kernighan & Ritchie, but that didn't make things any better...

And on looking at the code again, I realise that all I might be needing is an if statement that says if the number entered is equal to the mid (i.e. the 3rd item in the array), then to just print that out. Is that all I need to do? Because I tried it and that made the program worse, it started printing out the 'number found' lines infinitely.

The problem you are facing is because of placing the return statement before the print statement. A return statement means you want to duck out of the function with the given return value. This means, any statement after return won't be executed. Ideally your program should have only one exit point i.e. only one exit.

How about something like:

int binarySearch(int sortedArray[], int first, int last, int key) 
{
    int pos = -1;   
    while (first <= last) 
    {
        int mid = (first + last) / 2;
        if (key > sortedArray[mid]) 
            first = mid + 1;
        else if (key < sortedArray[mid]) 
            last = mid - 1;
        else
        {
            pos = mid;
            break; // we have found the element, no need to continue
        }
    }
    return pos;
 }

Also it is a bad practice to place display statements inside your processing algorithms except for debugging purposes. Call the search function in the main() function and depending on the return value, print the desired output.

Right, so I have written a few new functions, including one for the binary search as suggested. Annoyingly, it is this same function that I can't get to work... At the point where I call it in int main() I get a Segmentation Fault. I think it might be something small, but I can't for the life of me pick out what that is. Anybody who can care to shed some light on it for me please?

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

void insertArray(int n);
void sortArray(int n);
int binarySearch(int sortedArray[], int first, int last, int key);
 
int a[];

void insertArray(int n)
{
	int i;
	for (i = 0; i < n; i++)
		a[i]=i+1;
}

void sortArray(int n)	/* Using selection sort */
{
	int i, j, min, temp;
	
	for(i = 0; i < n-1; i++)
	{
		min = i;
		for(j = i+1; j < n; j++)
		{
			if (a[j] < a[min]) 
			{
				min = j;
				/* Swap the minimum value for first value*/
				temp = a[i];
				a[i] = a[min];
				a[min] = temp;
			}
		}
	}
}

int binarySearch(int sortedArray[], int first, int last, int key)
{
	int pos = -1;
	while (first <= last)
	{
		int mid = (first + last) / 2;
		if (key > sortedArray[mid])
			first = mid + 1;
		else if (key < sortedArray[mid])
			last = mid - 1;
		else
		{
			pos = mid;
			break; // Number has been found, exit loop
		}
      }
      return pos;
}

int main(void)
{
	int n = 5;
	int i, j, temp;
	int first, last, key, sortedArray[n], pos, mid;
		
	printf("\nWelcome to my binary search program.\n");
	printf("\nFirst we create an array of %d numbers\n", n);
	
	insertArray(n);
	
	printf("Then we sort the array\n");
	sortArray(n);
	
	/* Copy array values from a[] to sortedArray[]*/
	for (i = 0; i < n; i++)
		sortedArray[i] = a[i];
	
	printf("\nThe sorted numbers are: \n");
	for(i = 0; i < n; i++)
	{
		printf("Position [%d] = %d\n", i, sortedArray[i]);
	}
	printf("\n");
	
	// Assign values to beginning and end of the array
	printf("...then we assign values to the beginning and end of the array\n");
	first = 0;
	last = n-1;
	
	printf("This is the value of first: %d\n", first);
	printf("This is the value of last: %d\n", last);
	
	printf("\n Enter the number to be searched:");
	scanf("%d", &key);
	printf("\n\n");

	// This is the binary search
	binarySearch(sortedArray[n], first, last, key);
	if (pos = mid)
	{
		printf("\nNumber has been found!\n");
	}
	else
		printf("\nSorry number was not found.\n");
	
	
	return 0;
}

So to reiterate, the Segmentation Fault error occurs after line 92... Is there something rather obvious that I can't see that is causing the error?! All help is as always very much appreciated!

binarySearch(sortedArray, first, last, key);
if (pos == mid)
{
    printf("\nNumber has been found!\n");
}
else
    printf("\nSorry number was not found.\n");

Thanks sos. Now the program finds all the numbers in the array... the only problem is that it also finds numbers that aren't in there, and even letters. Which suggests that the binarySearch function is always ending in the 'else' part that says "pos = mid"... Any ideas how I can fix this please?

"pos = mid"...

You mean pos == mid.

I can't see why this code would work. You are using variables mid and pos in your main. But: they never get a value in main.
Now I here you thinking: "But I'm using them in binarySearch() ." Well no, the variables mid and pos from main are not in the same scope as the variables mid and pos from the function binarySearch(). So the statement if (mid == pos) will compare two undefined vars, which is a bad thing.
In the function binarySearch() you have this line: return pos; . Also it is declared as a function that should return a value, so this is correct. But when you call the function, you should give it something to write this return-var to. Like:

int pos2 = 0;
pos2 = binarySearch(sortedArray[], first, last, key);

Next problem:
You have a functiondefenition that expects an array of ints ([B]int[/B] binarySearch[B](int[/B] sortedArray[B][][/B], [B]int[/B] first, [B]int[/B] last, [B]int[/B] key[B])[/B]; . But you are calling it with only one element of an array, so one int in other words.

And there are a few more things wrong, but first correct these :icon_smile:

Edited 6 Years Ago by Nick Evan: n/a


Next problem:
You have a functiondefenition that expects an array of ints ([B]int[/B] binarySearch[B](int[/B] sortedArray[B][][/B], [B]int[/B] first, [B]int[/B] last, [B]int[/B] key[B])[/B]; . But you are calling it with only one element of an array, so one int in other words.

And there are a few more things wrong, but first correct these :icon_smile:

Regards Niek

Hey niek, thanks for the code critique. I have included a new variable to contain the value returned by the binarySearch function. However I'm not sure what you mean by I'm only calling the binarySearch function with one element of an array/one int? Would you please expand on that a little? Many thanks

I'm not sure what you mean by I'm only calling the binarySearch function with one element of an array/one int? Would you please expand on that a little? Many thanks

Allright: Your defenition is : int binarySearch([B]int sortedArray[],[/B] int first, int last, int key); But when you call the function, you call it like this: binarySearch([B]sortedArray[n],[/B] first, last, key); In your defenition your telling the compiler that the function binarySearch will take an array of ints as it's first argument. But when you call the function in main your calling it with the n'th element of an array, which is an int. (and only one) So the compiler will probably tell you that it cannot convert an int to int array[];.

Edited 6 Years Ago by Nick Evan: n/a

This article has been dead for over six months. Start a new discussion instead.