Solved

Binary Searches in an array (sorted already)

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

[Webinar] Learn How Hackers Steal Your Credentials

Do You Know How Hackers Steal Your Credentials? Join us and Skyport Systems to learn how hackers steal your credentials and why Active Directory must be secure to stop them. Thursday, July 13, 2017 10:00 A.M. PDT

Question has a verified solution.

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

Article by: Justin
In light of the WannaCry ransomware attack that affected millions of Windows machines, you might wonder if your Mac needs protecting. Yes, it does and here is how to do it.
In this blog post, we’ll look at how ClickHouse performs in a general analytical workload using the star schema benchmark test.
Michael from AdRem Software outlines event notifications and Automatic Corrective Actions in network monitoring. Automatic Corrective Actions are scripts, which can automatically run upon discovery of a certain undesirable condition in your network.…
Monitoring a network: why having a policy is the best policy? Michael Kulchisky, MCSE, MCSA, MCP, VTSP, VSP, CCSP outlines the enormous benefits of having a policy-based approach when monitoring medium and large networks. Software utilized in this v…

726 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