Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Binary Searches in an array (sorted already)

Posted on 1998-02-13
4
Medium Priority
?
157 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
  • 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

Will the future of mobile app development include the same trends as those most relevant today? Find out by checking out the 7 trends of the future.
MSSQL DB-maintenance also needs implementation of multiple activities. However, unprecedented errors can hamper the database management. In that case, deploying Stellar SQL Database Toolkit ensures fast and accurate database and backup repair as wel…
Screencast - Getting to Know the Pipeline
Is your OST file inaccessible, Need to transfer OST file from one computer to another? Want to convert OST file to PST? If the answer to any of the above question is yes, then look no further. With the help of Stellar OST to PST Converter, you can e…
Suggested Courses

810 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