Solved

data structure question

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

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
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.

856 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