Solved

data structure question

Posted on 2006-10-21
4
207 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 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

by:BrianGEFF719
ID: 17782385
Thanks!
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

912 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

Need Help in Real-Time?

Connect with top rated Experts

21 Experts available now in Live!

Get 1:1 Help Now