Binary search to find upper and lower bound values

Question

infantheartlyje 0 Light Poster

12 Years Ago

Hi folks,
I did a program to find a number at a lower bound position and upper bound position. For example,
this is my array values
1 1 2 3 5 5 5 5 7 8 9 10
if i search lower position for 5 , it will return 4 . and for upper bound it will return 7.

Actually i did a two function to find the numbers where it is locating for lower and upper bound.

int binarylower(int a[],int m,int l,int u)
{
	int mid,c=0;
   	if(l<=u)
	{
 	    	mid=(l+u)/2;
      		if(m==a[mid])
      		{
			c=m;
        	 	return binarylower(a,m,l,mid-1);
      		}
      		else if(m<a[mid])
		{	
        	  	return binarylower(a,m,l,mid-1);
      		}
      		else
		{     
			return binarylower(a,m,mid+1,u);
       		}
    	}

   	else
        	return l;
  }

int binaryupper(int a[],int m,int l,int u)
{
	int mid,c=0;
   	if(l<=u)
	{
 	    	mid=(l+u)/2;
      		if(m==a[mid])
      		{
			c=m;
        	 	return binaryupper(a,m,mid+1,u);
      		}
      		else if(m<a[mid])
		{	
        	  	return binaryupper(a,m,l,mid-1);
      		}
      		else
		{     
			return binaryupper(a,m,mid+1,u);
       		}
    	}

   	else
        	return u;
  }

Now i need only one function to find the lower and upper position. so i added extra parameter called 'mode' in that function. if mode value is 0, it will return lower position otherwise it will return upper position. This is my program

int binary(int a[],int m,int l,int u,int uorl)
{
	int mid,c=0;
   	if(l<=u)
	{
 	    	mid=(l+u)/2;
      		if(m==a[mid])
      		{
			c=m;
			if (uorl==0)
        	 		return binary(a,m,l,mid-1,0);
			else
				return binary(a,m,mid+1,u,1);
      		}
      		else if(m<a[mid])
		{	
        	  	return binary(a,m,l,mid-1,0);
      		}
      		else
		{     
			return binary(a,m,mid+1,u,0);
       		}
    	}

   	else
	{
		if (uorl==0)
		
        		return l;
		else
			return u;
	}
  }

But i couldn't get the correct answer from the above function. If any one knows the solution please help me

binary-search c

3 Contributors
7 Replies
4K Views
1 Day Discussion Span
Latest Post 12 Years Ago Latest Post by histrungalot

All 7 Replies

histrungalot 32 Junior Poster

12 Years Ago

On line 17 and 21 you are passing 0 for the uorl value all the time. You need to add an if else just like the others

// Code starting at line 15 in binary function,
// Fix it in both else ifs
else if(m<a[mid])
{
    if (uorl==0)
        return binary(a,m,l,mid-1,0);
     else
        return binary(a,m,l,mid-1,1);
}

Do both else ifs.

Edited 12 Years Ago by histrungalot because: n/a

histrungalot 32 Junior Poster

12 Years Ago

Wasn't thinking. Don't pass a hardcode value as the argumnet of to binary, pass uorl instead.

binary(a,m,l,mid-1,uorl);

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

infantheartlyje 0 Light Poster · Answer 1 · 2012-02-10T11:12:55+00:00

On line 17 and 21 you are passing 0 for the uorl value all the time. You need to add an if else just like the others
// Code starting at line 15 in binary function,
// Fix it in both else ifs
else if(m<a[mid])
{
    if (uorl==0)
        return binary(a,m,l,mid-1,0);
     else
        return binary(a,m,l,mid-1,1);
}
Do both else ifs.

Thank You for your reply. And i tried like this. but its not working.

if(m==a[mid])
      		{
			c=m;
			if (uorl==0)
        	 		return binary(a,m,l,mid-1,0);
			else
				return binary(a,m,mid+1,u,1);
      		}
      		else if(m<a[mid])
		{	
        	  	if (uorl==0)
				return binary(a,m,l,mid-1,0);
			else
				return binary(a,m,mid+1,u,1);
      		}
      		else
		{     
			if (uorl==0)
				return binary(a,m,l,mid-1,0);
			else
				return binary(a,m,mid+1,u,1);
       		}

histrungalot 32 Junior Poster · Answer 2 · 2012-02-10T11:34:35+00:00

Check you mid+1 and mid-1 combinations. It looks wrong. Upper is +1, -1, +1 and lower is -1, -1, +1.

infantheartlyje 0 Light Poster · Answer 3 · 2012-02-10T12:44:35+00:00

Check you mid+1 and mid-1 combinations. It looks wrong. Upper is +1, -1, +1 and lower is -1, -1, +1.

Now i changed my code like this.

int binary(int a[],int m,int l,int u,int uorl)
{
	int mid,c=0;
   	if(l<=u)
	{
 	    	mid=(l+u)/2;
      		if(m==a[mid])
      		{
			c=m;
			if (uorl==0)
        	 		return binary(a,m,l,mid-1,0);
			else
				return binary(a,m,mid+1,u,1);
      		}
      		else if(m<a[mid])
		{	
        	  	if (uorl==0)
				return binary(a,m,l,mid,0);
			else
				return binary(a,m,l,mid-1,1);
      		}
      		else
		{     
			if (uorl==0)
				return binary(a,m,mid+1,u,0);
			else
				return binary(a,m,mid,u,1);
       		}
    	}

   	else
	{
		if (uorl==0)
		
        		return l;
		else
			return u;
	}
  }

Now if my array value like this,
1 2 3 4 5 5 5 5 6 6 6 6 7 9 9

1. if i search 8 , means its giving segmentation fault. if it is not found means, i need position of number 7.

2. if i search 1(first number) means, its resulting 1 is not found at 0th position for both lower and upper case.

3. if search 9 (last number) means, if there is two 9 , it resulting correctly. It there is only one 9 means, it resulting correctly for lower position. for upper position search its resulting segmentation fault.

Why it is :-(

WaltP 2,905 Posting Sage w/ dash of thyme Team Colleague · Answer 4 · 2012-02-10T12:59:30+00:00

As I posted elsewhere

Try printing out a copy of your program, grab some paper and a pencil. Sit down at a desk or a table.
Start at the first executable statement in main() and follow the program statement by statement. Write down the values of all variables. Write down everything that is displayed. IOW, you be the computer and desk-check your program.
This is a fundamental part of programming -- checking your work.

Do the same with the algorithm you are trying to implement and note where your program and the algorithm seem to coincide -- and there they diverge.

All you seem to be doing is throwing new changes around without understanding what those changes really do. In fact you probably don't quite understand what the program is really doing at the moment (I know this because if you did know it would be obvious to you what to change).

Use the technique quoted above to understand what you wrote. And that will tell you what you need to fix.

histrungalot 32 Junior Poster · Answer 5 · 2012-02-10T23:34:56+00:00

There is a lot going on. The boundaries are the issue. See if this helps.

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

int binary(int a[],int size,int m,int l,int u,int uorl) {
   int mid,ret;
   if(l<=u ) {
      mid=(l+u)/2;
      if(m==a[mid]) {
         if (uorl==0){
            ret = binary(a,size,m,l,mid-1,uorl);
         }
         else{
            ret = binary(a,size,m,mid+1,u,uorl);
         }
      }
      else if(m<a[mid]) {	
         ret = binary(a,size,m,l,mid-1,uorl);
      }
      else {     
         ret = binary(a,size,m,mid+1,u,uorl);
      }
   }
   else {
      if (uorl==0){
         // Check boundaries
         if ( l > size || (l > u && m !=a[l] && u > 0)) 
            l--;  // Fix boundaries
         ret = l;
      }
      else{
         // Check boundaries
         if ( l < u || u < 0)
            u++; // Fix boundaries
         ret =  u;
      }
   }
   return ret;
}

int main(int argc, char **argv){
  int a[15] =  {1,2,3,4,5,5,5,5,6,6,6,6,7,9,9};
  //  int a[5] =  {1,3,5,5,6};
  //  int a[2] =  {1,2};
  int i,val;
  int upper=sizeof(a)/sizeof(int);
  if ( argc != 2 ){
     printf("Usage: %s <num to find>\n",argv[0]);
     return -1;
  }
  val = atoi(argv[1]); 
  printf("Look for: %d\n",val);
  printf("Lower: %d\n",binary(a,upper-1,val,0,upper-1,0));
  printf("Upper: %d\n",binary(a,upper-1,val,0,upper-1,1));
  return 0;
}

Binary search to find upper and lower bound values

Recommended Answers Collapse Answers

All 7 Replies

Recommended Answers