Be seen. Boost your questionâ€™s priority for more expert views and faster solutions

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.

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.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

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.

>> 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.

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[fir

//array[0]...array[NAME_LE

// 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.

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

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)/

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)/

k=middle;

t=0;

}

}

}else{

return -1;

found = false;

}

Thank you.

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;

}

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialname1

name0 name1 name2 name3 name4 name5

1

Press any key to continue_

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

C++

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

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