BrianGEFF719
asked on
data structure question
I'm not sure what this is called, I forget the name of this searching method, all i need is the name and a link with information on a searching method like this:
supose you have a sorted array.
suppose you want to search this array for an element.
Here is psuedocode:
int myArray[] = {1,2,3,4,5,6,7,8,9,10,11,1 2,13,14,15 ,16,17};
int start = 0;
int end = 16;
int search = 3;
int found = -1;
do
{
if ( myArray[ (start - end) / 2 ] < search )
start = (start - end) / 2 + 1;
else if ( myArray[ (start - end) / 2] == search)
found = (start - end) / 2;
else
end = (start - end) / 2 - 1;
} loop while (start != end && found == -1);
This is kind of like a "Divide and Conqour" approach, but what is this called? I remember studying something like this in a data structures class.
-Brian
supose you have a sorted array.
suppose you want to search this array for an element.
Here is psuedocode:
int myArray[] = {1,2,3,4,5,6,7,8,9,10,11,1
int start = 0;
int end = 16;
int search = 3;
int found = -1;
do
{
if ( myArray[ (start - end) / 2 ] < search )
start = (start - end) / 2 + 1;
else if ( myArray[ (start - end) / 2] == search)
found = (start - end) / 2;
else
end = (start - end) / 2 - 1;
} loop while (start != end && found == -1);
This is kind of like a "Divide and Conqour" approach, but what is this called? I remember studying something like this in a data structures class.
-Brian
ASKER
Hi sunnycoder,
I see the Order of Magnitude of such a search is Log base 2 of N, which is very fast.
Let me just ask you this one last thing, the fastest search time you can get is an order of magnitude 1 which can only happen in a Hash Table, is this correct?
-Brian
I see the Order of Magnitude of such a search is Log base 2 of N, which is very fast.
Let me just ask you this one last thing, the fastest search time you can get is an order of magnitude 1 which can only happen in a Hash Table, is this correct?
-Brian
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thanks!
This is binary search
http://en.wikipedia.org/wiki/Binary_search
Cheers!
sunnycoder