Solved

Binary Searches in an array (sorted already)

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

Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

Question has a verified solution.

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

FAQ pages provide a simple way for you to supply and for customers to find answers to the most common questions about your company. Here are six reasons why your company website should have a FAQ page
Employees depend heavily on their PCs, and new threats like ransomware make it even more critical to protect their important data.
Windows 10 is mostly good. However the one thing that annoys me is how many clicks you have to do to dial a VPN connection. You have to go to settings from the start menu, (2 clicks), Network and Internet (1 click), Click VPN (another click) then fi…
This video shows how to use Hyena, from SystemTools Software, to bulk import 100 user accounts from an external text file. View in 1080p for best video quality.

785 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