?
Solved

data structure question

Posted on 2006-10-21
4
Medium Priority
?
212 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
Suggested Courses

752 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