Binary search

[capablanca]

How can I use binary search into 2D arrays?. I want to search a number row by row

[donbock]

Binary search only works if the list is presorted. How is the 2D array ordered?

[capablanca]

binary search

Hi donbock.
The 2D array is sorted and I want to search a number by row, besides I want to continue the search even if the number is found maybe there is another same number and when the all matrix is searched I want to display the rows where that number appear.
I will appreciate any advice. C++ if there any code, thanks.

[capablanca]

binary search

Hi donbock.
I forgot to tell you that the rows into the 2D array are ordered ascending.

[donbock]

The 2D array is sorted and I want to search a number by row

Is each row sorted individually or is the entire 2D array sorted? That is, is it like this:

row 1:  AAACDK...
row 2:  BCDJM...
...

or like this:

row 1:  AAAABBCDE...
row 2:  GHKM...
row 3:  PRU...
...

If the rows are sorted individually (first example), then you need to repeat the binary search on each row. The binary search function only operates on a 1D array.

If the entire 2D array is sorted (second example), then a single pass through the binary search function is sufficient, but the binary search function must explicitly handle the 2D array.

What is your policy for upper and lowercase characters? Is 'A' the same as 'a'? If not, which is greater? Are you sure the array sort order is consistent with this policy?

Please recap the basic algorithm for binary search.

[capablanca]

Is each row sorted individually or is the entire 2D array sorted? That is, is it like this:

row 1:  AAACDK...
row 2:  BCDJM...
...

or like this:

row 1:  AAAABBCDE...
row 2:  GHKM...
row 3:  PRU...
...

If the rows are sorted individually (first example), then you need to repeat the binary search on each row. The binary search function only operates on a 1D array.

If the entire 2D array is sorted (second example), then a single pass through the binary search function is sufficient, but the binary search function must explicitly handle the 2D array.

What is your policy for upper and lowercase characters? Is 'A' the same as 'a'? If not, which is greater? Are you sure the array sort order is consistent with this policy?

Please recap the basic algorithm for binary search.

Hi donbock
Thanks for reply my post.
My 2D array is your first example(the rows are sorted individually) so like you said I have to repeat the binary search on each row and that is my real problem
how to do it into 2D array.I have more than a week trying to figure it out but I can't do it. Can you give me an example in C++ please, thanks.

[jkmyoung]

Ignore the fact that it is 2-d for the moment. Try doing your search on a single array (eg one row of the 2d array). Are you getting the results correctly for the first row? If not what results are you getting?

Clarifying question:
Are there any duplicated values within a single row of the array?

[capablanca]

Ignore the fact that it is 2-d for the moment. Try doing your search on a single array (eg one row of the 2d array). Are you getting the results correctly for the first row? If not what results are you getting?

Clarifying question:
Are there any duplicated values within a single row of the array?

Hi jkmyoung
I know how to do a search on a 1D array using binary search but I do not know how to do it into a 2D array . I have C++' books, I search the internet and I can not find a single example about this matter, all the examples I had found are the binary search in 1D array .
The expert donbock told me that is possible to do the binary search into 2D array, in my program the rows are sorted in ascending and each row are individually, he told me I have to repeat the binary search on each row but I just do not know how to do it.
About your question: Yes there are duplicated values within a single row of the array but I think that is not important because what I want the program do it is to search an integer number and display on the console the row in which that number belong.
Could you give me an example of a function doing a binary search into 2D array in C++. Thanks for reply my post.

[jkmyoung]

pseudo code

int[depth][width] array 
int searchTerm

for(i = 0; i < depth; i++)
  if BinarySearch(searchTerm, array[i], 0, width - 1) returns found, print "row" +  i

This searches the first row, then the second row, etc...

[capablanca]

pseudo code

int[depth][width] array 
int searchTerm

for(i = 0; i < depth; i++)
  if BinarySearch(searchTerm, array[i], 0, width - 1) returns found, print "row" +  i

This searches the first row, then the second row, etc...

Hi jkmyoung
Can you help me to apply your pseudo code in this program because honestly I just got about two months studying by myself C++ . THANKS
#include <iostream>
#include <iomanip>

using namespace std;

const int depth = 4;
const int width = 5;

int BinarySearch(in t [], int, int);

int main()
{
cout<<endl;
int array[depth][width] = {{5,10,22,32,45 },{20,23,34,40, 56},
{12,14,16,34,45 },{2,6,34,45,47 }};
int num;// location;

for(int i=0; i<depth; i++)
{
for(int j=0; j<width; j++)
{
cout<<setw(5)<< array[i][j];
}
cout<<endl;
}
cout << "Enter the number you are searching for: ";
cin >> num;



location= BinarySearch(ar ray, width, num);

if (location > -1)
cout << "The number was found at index location "
<< location << endl;
else
cout << "The number was not found in the list\n";

return 0;
}

int BinarySearch(in t list[], int size, int key)
{
int left, right, midpt;

left = 0;
right = size - 1;

while (left <= right)
{
midpt = (int) ((left + right) / 2);
if (key == list[midpt])
{
return midpt;
}
else if (key > list[midpt])
left = midpt + 1;
else
right = midpt - 1;
}

return -1;
}

// pseudo code

// int[depth][width] array
// int searchTerm

// for(i = 0; i < depth; i++)
// if BinarySearch(se archTerm, array[i], 0, width - 1) returns found, print "row" + i

[donbock]

Please enclose your source code in CODE tags. (Select the code, then press the "#" button at the top of the edit box.)

Don't let the 2D array confuse you. Arrays Revealed will demystify them.

int array[4][5];

This is an array of four 1D arrays, each of which has 5 elements. Each of these four 1D arrays can be sent to your BinarySearch function. That is, you need to call BinarySearch four times. The code you posted only calls it once.

[jkmyoung]

Eg:
location= BinarySearch(ar ray[0], width, num);
calls it on the first row of the 2d array. Call Binary search on all of the rows.

[capablanca]

Please enclose your source code in CODE tags. (Select the code, then press the "#" button at the top of the edit box.)

Don't let the 2D array confuse you. Arrays Revealed will demystify them.

int array[4][5];

This is an array of four 1D arrays, each of which has 5 elements. Each of these four 1D arrays can be sent to your BinarySearch function. That is, you need to call BinarySearch four times. The code you posted only calls it once.

First of all I want to acknowledge the help they have given me the expert and the moderator donbock and jkmyoung by their knowledge, the first theoretical and the second for his specific example, both responses have the qualification the best answer, sinseramente my deepest thanks to the two and also would like to congratulate the person or persons had the idea to create this website invaluable for people like me can find help in this beautiful world that is the programming and compare it to the game of chess, because both with a little imagination can one achieve their goal. Thank you very much.

[capablanca]

Eg:
location= BinarySearch(ar ray[0], width, num);
calls it on the first row of the 2d array. Call Binary search on all of the rows.

First of all I want to acknowledge the help they have given me the expert and the moderator donbock and jkmyoung by their knowledge, the first theoretical and the second for his specific example, both responses have the qualification the best answer, sinseramente my deepest thanks to the two and also would like to congratulate the person or persons had the idea to create this website invaluable for people like me can find help in this beautiful world that is the programming and compare it to the game of chess, because both with a little imagination can one achieve their goal. Thank you very much.