Solved

Binary Searches in an array (sorted already)

Posted on 1998-02-13
4
132 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 50 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

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Performance in games development is paramount: every microsecond counts to be able to do everything in less than 33ms (aiming at 16ms). C# foreach statement is one of the worst performance killers, and here I explain why.
Find out what the Office 365 disclaimer function is, why you would use it and its limited ability to create Office 365 signatures.
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …
You have products, that come in variants and want to set different prices for them? Watch this micro tutorial that describes how to configure prices for Magento super attributes. Assigning simple products to configurable: We assigned simple products…

747 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

15 Experts available now in Live!

Get 1:1 Help Now