?
Solved

data structure question

Posted on 2006-10-21
4
Medium Priority
?
217 Views
Last Modified: 2010-04-01
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
Comment
Question by:BrianGEFF719
  • 2
  • 2
4 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 17782364
Hi BrianGEFF719,

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

Cheers!
sunnycoder
0
 
LVL 19

Author Comment

by:BrianGEFF719
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

by:
sunnycoder earned 2000 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

by:BrianGEFF719
ID: 17782385
Thanks!
0

Featured Post

Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
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.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

616 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question