Binary Search Using Recursion on 2-D Array

[artorius]

This is my problem...hopefully somebody can help me out with this.

This is what I am supposed to be doing:
Recursive Binary Search of 2-dimensional array:
Load a 30x20 two-dimensional array of ints with values from the file “values.txt”. The file contains 900 numbers in order. Once the array is loaded, allow the user to select a number to find in the array. Call a recursive routine that searches for the number, then display the entire array and the location of the number, if found. If the number is not found, display the array and notify the user that the number was not found. The user must be able to select numbers to find until they wish to quit.
Recursive Search Details: This search must be done in two steps, both are recursive. First, narrow the search to the row where the item must be located. Second, search that row for the item. You may use one recursive function or, if you wish, you may use two recursive routines, one that handles the first step and then calls another that handles the second step. In any case, you must return a Boolean value that indicates the success or failure of the search, and you must use call-by-reference parameters to store the location of the item if found. If the number is not found, these parameters need not be changed.

This is what I have so far:

int rBinarySearch(int Values[][20], int first, int last, int key) 
{
	
	first = Values[0][0];
	last = Values[29][19];
	if(first <= last)
	{
		int mid = (first + last) / 2;
	}
	if(key == Values[][mid])
	{
		return (mid);
	}else if(key < Values[][mid])
	{
		return rBinarySearch(Values, first, mid-1, key);
	}else 
	{
		return rBinarySearch(Values, mid+1, last, key);
	}
	return false;
}

for some reason when I compile I get errors about illegal if elses...don't know if my spacing is off or what but I played around with it for a while. Also how do I display the location of the number if found when I display the array and is the rest correct in my coding? Also how do I return a bool if not found when I have to return (first +1)? Am I on the right track and what am I doing wrong/ how do I fix it? Any help would be greatly appreciated.

[StuXYZ]

Note 100% certain I follow what you are trying to do.
But some points:

(a) C++ is almost space insensitive. The only areas you have to worry are in the middle of keywords e.g. cla ss A { } is not acceptable, nor in the middle of stuff like operator<< e.g. std::cout< <"Hello"<<std::endl; (b) Consider your code:

if(first <= last)
{
int mid = (first + last) / 2;
}

This creates a variable mid. BUT mid has scope ONLY within the braces
e.g. only for ONE line of code. Therefore this if and the creation of mid is useless.

Then you try to use a mid LATER but that does't exist so you get errors.

(c) you pass values into your function e.g. first and last, but immediately you assign them to some value from your matrix. This negates the purpose of calling them into the function.

if(key == Values[][mid])

This line does not work since you have to define the first array index.

Please start with something a lot simpler, try just printing the array, then swapping it around. Doing stuff in stages is often quicker than doing the problem in hand.

[artorius]

Thank you for your reply and your remarks did help. As for printing and altering the array I use that in another function and it works well for what I need it to now. I still can't figure out exactly how to go about this binary search. I was thinking about taking in the number and then determining which row of the array it is in and then searching that row. My understanding is there I think but the problem comes when I try to implement code as you can see. Is it possible to divide by the number of rows and then multiple by the number of rows to figure out the exact row? For ex. a 9x9 array, you would divide by 3 and multiply by 3 to determine which section of rows to start looking.

[StuXYZ]

Actually, if you are doing a binary search, make 100% certain that you understand the algorithm in 1D. That is important since 2D array can be easily thougth of as a 1D array. The binary search can be done recursively
but let us start with the simple 1d binary search.

It REALLY helps to do this on paper with three coloured counters that you place on the number the index points to.

consider a set of numbers that are ordered, for simpicity consider
0-99. in linear order.

Now set target = 43  (anynumber between 0-99 will do)
        set first =0 
        set last = 99
        set mid = (first+last)/2 = 49 (remember integer arithmatic)
        
// Loop over
            while(mid!=target)
               {
                  if (mid>target)      // obviously last>mid and it is also LOTs 
                     last=mid;          // bigger than target
                  else  
                      first=mid;
                  mid=(first+last)/2
              }

Understand how THIS works.

Now continue to see that if you have an ordered array of 100 points.
Then first,mid,last represent the array index and the values in the array are only used in the test to see if array[mid]>target.

This is only a fraction away from a 2D array, and slight modifications away from a recursive function.

[artorius]

Thank you for your posts. After playing with it for a couple hours I figured it out! Thanks again! Here it is...it works for what I need but please critique my style and formatting.

int binarySearch(int Values[30][20],int row,int first,int last,int target)
{
    int middle= (first+last)/2;
    
    if(first>last)
       return -1;
       
    if(Values[row][middle]==target)
       return middle;
        
    if(Values[row][middle]>target)
        return binarySearch(Values,row,first,middle-1,target);
        
    return binarySearch(Values,row,middle+1,last,target);
}
int binarySearchRow(int Values[30][20],int first,int last,int size,int target)
{
    if(first>last)
       return -1;
       
    int middle= (first+last)/2;

    if(Values[middle][0]<= target && Values[middle][size-1]>=target)
        return middle;
        
    if(Values[middle][0]>target)
        return binarySearchRow(Values,first,middle-1,size,target);
    
    return binarySearchRow(Values,middle+1,last,size,target);
}
bool search(int Values[30][20],int target,int &x,int &y)
{
     x= binarySearchRow(Values,0,30,20,target);
     
     if(x==-1)
        return 0;
    
     y = binarySearch(Values,x,0,30,target);

     if(y==-1)
         return 0;
     return 1;
 }

Thanks again