# 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,12,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
LVL 19
###### Who is Participating?

Commented:
Hi Brian,

Yes ... Fastest is constant time search ... Ideal hash table will give you such search times or an arrangement like ...
Given k numbers in the range 0-n, define an array of 0 to n and if a number p is present, set the corresponding pth index to else it is 0. Here you can tell in constant time if a number is present or not but it potentially wastes a lot of memory.

Cheers!
sunnycoder
0

Commented:
Hi BrianGEFF719,

This is binary search
http://en.wikipedia.org/wiki/Binary_search

Cheers!
sunnycoder
0

Author Commented:
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
0

Author Commented:
Thanks!
0
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.