Binary recursive search algorithm in C

Question

Ok, that's why I am assigned a function

int bin(int value, int size, int array[]) 

I have to find the "value" inside the "array []", but the problem here is that in most cases we have something like strings

 int bin(int value, int max, int min, int array[]) 

Recursion, logically, is much simpler in this part due to the fact that I can still pass the number I was on, and also remember the size of the array.

 int bin(int array[], int value, int min, int max) { if(max < min) return -1; else { int mid = min + (max - min)/2; if(array[mid] > value) return bin(array, value, min, mid-1); else if(array[mid] < value) return bin(array, value, mid+1, max); else return mid; } 

But since I can only pass 1 integer, how exactly would I edit this algorithm? Essentially, I could only do something like this, but I KNOW that this will not work logically. Is there a way, however, that I can see the size of the array? I tried, but the numbers do not crunch correctly.

  int bin(int array[], int value, int size) { int mid = size/2; if(array[mid] > value) return bin(array, value, size-(size/2)); else if(array[mid] < value) return bin(array, value, size+(size/2)); else return mid; } 

Answer 1

You also need to explicitly pass the base:

 int bin(int array[], int value, int size) { int mid = size/2; if(array[mid] > value) return bin(array, value, size/2); else if(array[mid] < value) return bin(&array[mid], value, size/2); else return mid; } 

pay attention to "& array [mid] in the field" if (array [mid] <value] "

every time you have the right half of the array to search using base + offset min min / max index

Answer 2

The purpose of a method with a different set of arguments is to simplify the method call for the user. This is very common in recursion.

There is a public method available to the user that has int bin(int value, int size, int array[]) .

Then there should be a private, internal helper method using int bin(int value, int max, int min, int array[]) .

The fact is that someone calling this method will want to pass the size of the array, not the beginning and end index (because for them the starting index should always be 0, the end should always be size-1) and it’s bad practice to have a method with arguments that are set this way.

A helper method with start and end values ​​(min and max) is used in recursive calls for more efficient calculations and hides unnecessary arguments from the user.

Your method should look something like this:

 int bin(int value, int size, int array[]) { return bin(value, size - 1, 0, array); } 

Answer 3

 int * binSearch (int *arr,int size, int num2Search) { if(size==1) return ((*arr==num2Search)?(arr):(NULL)); if(*(arr+(size/2))<num2Search) return binSearch(arr+(size/2)+1,(size/2),num2Search); if(*(arr+(size/2))==num2Search) return (arr+(size/2)); return binSearch(arr,(size/2),num2Search); } 

in my function you get the same parameters and return the address of the value.