[2 days left] What’s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
?
Solved

Recursive binary search char*

Posted on 2004-10-29
14
Medium Priority
?
604 Views
Last Modified: 2008-02-01
I am trying to implement a recursive binary search function that takes 4 arguments.
void binary_search(char target[], int first, int last, int index);

The target will be the name that is stored in an array of char.
The problem I have is whenever it encounter names with same first char, the problem will go into an infinited loop.
I tried using the algorithm to search for an array of integer, but it doesn't work for my case.

The following is what I did:

midder = first+last/2;
int i=0, k=0;
char *array = //something
while(first <= last){
        if(target[i] == array[k]){
               i++, k++; //compare other characters in the array
         }else if (target[i] < array[k])
                last = middle - (size of name in array);
                middle =( middle/size of name in array/2)*size of the name in array
                k = middle;
                i = 0;
         }else if (target[i] > array[k]){
                first = middle + size of name in array
                middle = (first/size of name in array)+((last - first)/size of name in array/2)*size of name in array)
                k = middle;
                t = 0;
         }
}

I see a lot of redundant steps in this program. So, I am thinking of implementing a recursive binary search which will be more efficient that this.
Any help with explainination will be appreciated.
0
Comment
Question by:icysmarty
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 4
  • 3
  • +2
14 Comments
 
LVL 86

Expert Comment

by:jkr
ID: 12447900
>>I am thinking of implementing a recursive binary search which will be more efficient that this

Why reinventing the wheel? Use 'std::binary_search()': http://www.sgi.com/tech/stl/binary_search.html
0
 

Author Comment

by:icysmarty
ID: 12447945
That stl binary search returns bool value. Instead, I need to retrieve the index of the item once it is found in the array.
0
 
LVL 4

Expert Comment

by:anthony_w
ID: 12448935
You can use std::lower_bound, which will return a pointer to the array entry where the searched-for term *would be*. You can then check to see if this is indeed the right entry, and get the index from the pointer if it is, or return an error if not.
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 9

Assisted Solution

by:zaghaghi
zaghaghi earned 800 total points
ID: 12450394
Hi,

I replace your function with this :

int binary_search(char target[], int first, int last, int val)
{
     if(last<first)
          return -1;
     int mid = (first + last) / 2;
     if(target[mid]<val)
          return binary_search(target, mid, last, val);
     else if(target[mid]>val)
          return binary_search(target, first, mid, val);
     else
          return mid;
}

have a good searching day.
0
 
LVL 9

Expert Comment

by:zaghaghi
ID: 12450396
note :

>>>midder = first+last/2;

must replace with midder = (first+last)/2;

good luck

0
 

Author Comment

by:icysmarty
ID: 12450559

>>     if(target[mid]<val)
          return binary_search(target, mid, last, val);

what is the val you mean in this if statement?
The index variable in my function will return the index in the array where the target is found.
The target array will be compared with a buffer array which has the data from a file.

target[mid] is a character and val is an integer, how can I compare this two?

array[k] is an array with fixed length data.
Say each field occupies 10 bytes.
In the array, the data will appear to be like this :
'A''L''E''X' ' ' ' ' ' ' ' ' ' ' ' ' 'B''E''N''N''Y'' ' ' ' ' ' ' ' ' ' 'B''O''B''O'' '' '' '' '' '' '
So say mid will be pointing 'B'(of Benny) then the function needs to move forward to check the other characters.
That's where i stuck.
0
 
LVL 9

Expert Comment

by:zaghaghi
ID: 12455892
Hi,

I wrote this function by these rules that target is an int array, val is the valu that i was to find it, and my function return the index of finded valu in target array;

so,
#define NAME_LEN   10

//this function compare target[first]...target[first+NAME_LEN] with
//array[0]...array[NAME_LEN] and return these values:
// if target < array return negetive number
// if target > array return positive number
// if target == array return 0
int check(char target[], int  start)
{
     int i;
     for(i=0; i<NAME_LEN; i++)
     {
          if(target[i]==array[i])
               continue;
          else
               return target[i]-array[i];
     }
     return 0;
}

int binary_search( char target[], int first, int last)
{
     if(last<first)
          return -1;
     int mid = ( first + ( last / NAME_LEN ) ) / 2;
     mid *= NAME_LEN;
     int sw = check(target,  mid);
     if(sw < 0)
          return binary_search(target, mid, last);
     else if(sw > 0 )
          return binary_search(target, first, mid);
     else // sw == 0
          return mid;
}


Have a good programming day.
0
 
LVL 9

Expert Comment

by:jhshukla
ID: 12455899
>> Say each field occupies 10 bytes
that helps a lot.

why "void binary_search(char target[], int first, int last, int index)"? don't you want to pass in the array_to_search_ in and array_to_search_ for? and why pass the index? you should be returning the index.

int binary_search(char *array, char *target, int first, int last){
  if(first > last) return -1;

  int middle = (first+last)/2;
  int comp = strncmp(&array[middle], target, strlen(target);
  if(comp == 0) return middle;
  if(comp < 0) return binary_search(array, target, middle, last);
  else return binary_search(array, target, first, middle-10);
}

note that first, last and middle must be multiples of 10 (or whaterver field length you choose). also note (middle-10) instead of the usual (middle-1).

jaydutt
0
 
LVL 9

Expert Comment

by:jhshukla
ID: 12455901
sorry, zaghaghi got there first.
0
 

Author Comment

by:icysmarty
ID: 12455908
strcmp do not work with both arrays. I tried. So, I implement the comparrison function, and again, it looks redundant.
The recursion doesn't as I tried. So, this is my binary search. Can you see a way to make it recursive?

if(first <= last){
      while(first <= last && !found ){      //begins binary search
            if(target[t] == IBuffer[k]){      //check for next characters
                  while(IBuffer[k] != 32)
                  {            
                        if(target[t] == IBuffer[k])
                        {
                              found_count= found_count+1;
                              
                        }else if(target[t] < IBuffer[k])
                        {
                              last = middle-22;
                              middle = ((middle)/22/2)*22;
                              k=middle;
                              t=0;
                              break;
                        }else{
                              first = middle+22;
                              middle = ((first/22)+((last-first)/22/2))*22;
                              k=middle;
                              t=0;
                              break;

                        }
                        t++;k++;
                                          
                  }
                  if(found_count == t){
                        found = true;
                        RRN = get_RRN(middle+16);
                        return middle;
                  }
                  found_count = 0;
             }else if(target[t] < IBuffer[k]){      
                  
                  last = middle-22;
                  middle = ((middle)/22/2)*22;
                  k=middle;
                  t=0;
                  
            }else if(target[t] > IBuffer[k]){
                  
                  first = middle+22;
                  middle = ((first/22)+((last-first)/22/2))*22;
                  k=middle;
                  t=0;
            }
      }
      }else{
            return -1;
            found = false;
      }

Thank you.
0
 
LVL 9

Accepted Solution

by:
jhshukla earned 1200 total points
ID: 12455957
#include <iostream>
using namespace std;

int binary_search(char *array, char *target, int first, int last){
  if(first > last) return -1;

  int middle = (first+last)/2;
  int comp = strncmp(array + middle*10, target, strlen(target));

  if(comp == 0){
    return middle;
  }
  if(comp < 0){
    return binary_search(array, target, middle+1, last);
  }
  else{
    return binary_search(array, target, first, middle-1);
  }
}

int main()
{
    char target[] = "name1";
    char array[] = "name0     name1     name2     name3     name4     name5     ";
    cout << target << endl << array << endl;
    cout << binary_search(array, target, 0, 5) << endl;
    return 0;
}
0
 

Author Comment

by:icysmarty
ID: 12455969
strncmp causes an access violation to the program
0
 
LVL 9

Expert Comment

by:jhshukla
ID: 12455987
nope. it doesn't. I ran it. here's sample output:

name1
name0     name1     name2     name3     name4     name5
1
Press any key to continue_
0
 

Author Comment

by:icysmarty
ID: 12456066
Cool.
The problem is with the middle value.
I have changed it according to the size of the data structure.
Also, I changed it to static int instead of int cause only the first middle will be ( first + last)/2
Thank you for all the helps.
I think I should give credit to zaghagi too.

Solving the searching problem here comes the sorting problem. I have posted it in another post. Take a look if you have any clue about that. Here is the link.
http://www.experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_21189206.html
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

649 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question