Solved

data structure question

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

Technology Partners: 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

Suggested Solutions

Title # Comments Views Activity
IdTCPClient1->Disconnect(); not working 3 87
Find Visual Studio Tools 2 126
How to gracefully close the c++ 11 thread? 3 123
c++ aadding data to a list box vs2005 mfc project 7 14
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

730 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