?
Solved

Binary Searches in an array (sorted already)

Posted on 1998-02-13
4
Medium Priority
?
149 Views
Last Modified: 2010-04-16
Last one, I promise....

I have to do a lab for school.  I need help with making a binary search in a one-dimensional array that has been sorted using the bubble method.  i know about the first and last then average, etc., but i have no idea actually how to code that. and everthing....please help
0
Comment
Question by:weinrj
[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
4 Comments
 
LVL 2

Expert Comment

by:kellyjj
ID: 1217319
when you say binary sort, are you talking about comparing the byte value of each element of the array?
0
 

Author Comment

by:weinrj
ID: 1217320
I meant a binary search.  My teach. calls it that because it
cuts it half in time with sequentional search.  I believe it
takes top and last number, averages, etc. until it found it.
0
 
LVL 1

Accepted Solution

by:
Nexial earned 150 total points
ID: 1217321
From D. Knuth "The Art of Computer Programming", Volume 3 (first edition): P. 407


"Algorithm B (Binary Search).   Given a table of records R1, R2,...,Rn whose keys are in increasing order K1 < K2 < ... < Kn then this algorithm searches for a given argument K.

B1. [Initialize.] Set l <- 1, u <- N

B2. [Get midpoint.] (At this point we know that if K is in the table, it satisfies Kl <= K <= Ku.  A more precise statement of the situation appears in exercise 1 below.)  If u < l, the algorithm terminates unseuccessfully.   Otherwise set i <- floor((l+u/2)), the approximate midpoint of the relevant table area.

B3. [Compare.] If K < Ki goto B4;  if K > Ki, goto B5; and if K=Ki the algorithm terminates successfully.

B4. [Adjust u.] Set u <- i -1 and return to B2.

B5. [adjust l.] Set l M- i + 1 and return to B2."
======================================================
u = upper bound,
l = lower bound
The floor function produces the greatest integer <= its argument.

The materials in exercise 1 are not needed, as they deal with the tightness of the bounding conditions, and are irrelevant to the code.

"Although the basic idea of binary search is comparatively straightforward, the details can be somewhat tricky, and many good programmers have doe it wrong the first few times they tried.   One of the most popular correct forms of the algorithm makes use of two pointers, l and u, which indicate the current lower and upper limits for the search"

BE ESPECIALLY CAREFUL OF THE +/- 1 being added to the pointers in B4 and B5.

0
 

Author Comment

by:weinrj
ID: 1217322
thanks....it was a tad too confusing, i am in computer science
I in H.S.  I will experiment what you want me to do.  
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say 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

This is a fine trick which I've found useful many times, when you just don't want to accidentally run a batch script or the commands needs administrator rights.
The well known Cerber ransomware continues to spread this summer through spear phishing email campaigns targeting enterprises. Learn how it easily bypasses traditional defenses - and what you can do to protect your data.
This tutorial will teach you the special effect of super speed similar to the fictional character Wally West aka "The Flash" After Shake : http://www.videocopilot.net/presets/after_shake/ All lightning effects with instructions : http://www.mediaf…
In this video, Percona Director of Solution Engineering Jon Tobin discusses the function and features of Percona Server for MongoDB. How Percona can help Percona can help you determine if Percona Server for MongoDB is the right solution for …
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