Solved

data structure question

Posted on 2006-10-21
206 Views
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
0
Question by:BrianGEFF719
• 2
• 2

LVL 45

Expert Comment

ID: 17782364
Hi BrianGEFF719,

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

Cheers!
sunnycoder
0

LVL 19

Author Comment

ID: 17782373
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

LVL 45

Accepted Solution

sunnycoder earned 500 total points
ID: 17782380
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

LVL 19

Author Comment

ID: 17782385
Thanks!
0

Featured Post

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.