UNIX Socket FAQ

A forum for questions and answers about network programming on Linux and all other Unix-like systems

You are not logged in.

  • Index
  • » C
  • » Binary Search

#1 2007-07-09 02:31 PM

aaronc
Member
Registered: 2007-04-25
Posts: 8

Re: Binary Search

Hi,
Below is an example of Binary Search using pointers, I do not understand the purpose of line

return pMid-array;

. Shouldn't we just return pMid because wouldn't the address of array change everytime we do pStart=pMid+1 as pStart and array point to each other?
Please help.
Thanks

int binaryS (int *array,int size, int element) {
int *pStart=array, pEnd=array+size-1;
int *pMid;
while (pEnd>=pStart) {
pMid=pStart+(pEnd-pStart)/2;
if(*pMid == element)
[b]return pMid-array;[/b]
else if (*pMid < element)
pStart=pMid+1;
else
pEnd=pMid-1;
}
return –1;

Offline

#2 2007-07-09 03:24 PM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,239

Re: Binary Search

binaryS() returns the array index, not the pointer to the element, so it converts the pointer to the index, which is what the "pMid - array" does.

Offline

#3 2007-07-10 06:34 AM

aaronc
Member
Registered: 2007-04-25
Posts: 8

Re: Binary Search

Hi,
I am really confused, I thought that pMid should be the index of the array as it contains the memory address for a particular value?

Offline

#4 2007-07-10 12:52 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,839
Website

Re: Binary Search

No, "pMid" is a pointer...  Yes, it contains the (virtual) memory address...  An index
is different: it's a simple integer value giving the relative location within the array...
(Whereas the pointer gives the absolute location within your virtual address space...)
The two can be converted between via:

type *base; /* the base of your array of whatever type */
type *ptr;
int idx;
/* ... */
ptr = base + idx;  /* which is the same as &(base[idx]) */
/* ..and, the obvious reverse... */
idx = ptr - base;

Offline

#5 2007-07-10 01:00 PM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,239

Re: Binary Search

int binaryS(int *array, int size, int element)
{
	int pStart = 0;
	int pEnd = size - 1;
	int pMid;
	while (pEnd >= pStart){
		pMid = pStart + (pEnd - pStart) / 2;
		if (array[pMid] == element)
			return pMid;
		else if (array[pMid] < element)
			pStart = pMid + 1;
		else
			pEnd = pMid - 1;
	}
	return -1;
}

Offline

  • Index
  • » C
  • » Binary Search

Board footer

Powered by FluxBB