Binary search, Computer Engineering

Assignment Help:

Binary Search

Now that the basic framework is working, it is time to begin implementing a few alternative search functions. Each of these search algorithms have strengths and weaknesses, depending on the distribution of the input and the search keys used. The classic solution to this problem is binary search. Binary search is a divide-and-conquer algorithm. See Levitin [2007] pp 162 for a detailed description of this algorithm.

ALGORITHM BinarySearch (A[0 . . . n - 1], k)
// Non-recursive binary search in an ordered list.
// INPUT : An array A[0 . . . n - 1] of ordered elements, and a search key k.
// OUTPUT : an index to the position of k in A if k is found or -1 otherwise.
1: l ← 0; r ← n - 1
2: while l ≤ r do
3: m ← ⌊(l + r)/2⌋
4: if A[m] = k then
5: return m
6: else if k < A[m] then
7: r ← m- 1
8: else

9: l ← m+ 1

10: return -1

Algorithm BinarySearch shows the pseudocode for this solution. Implement the algorithm.


Related Discussions:- Binary search

Why smtp used as transfer protocol for web pages, Can SMTP be used as trans...

Can SMTP be used as transfer protocol for Web pages? Why? SMTP is an easy mail transfer protocol. This uses ASCII text for all communications. SMTP needs reliable delivery- the

What are the disadvantages of a vpn implementation, What are the Disadvanta...

What are the Disadvantages of a VPN implementation The greatest disadvantage of a VPN implementation is its non-flexibility to accept unknown locations. VPN works extremely wel

What do you mean by single construct in fortan, Q. What do you mean by Sing...

Q. What do you mean by Single Construct in FORTAN? Single construct specifies the associated structured block is executed by just one thread in team (not essentially the master

Explain the structured design of system, Q. Explain the Structured Design o...

Q. Explain the Structured Design of system? Structured Design utilizes graphic description (Output of system analysis) and focuses on development of software specifications.

Computers and cntrol, Define open and closed loop cotrol systems.Explain di...

Define open and closed loop cotrol systems.Explain difference between time varying and time invariant control system wth suitable example

Give an example of problem statement, Give an example of Problem Statem...

Give an example of Problem Statement You should understand here that you are looking for a statement of requirements, not a proposal for the solution. OOA specifies structu

Rapid appllication development, Explain clearly the four stages in the Rapi...

Explain clearly the four stages in the Rapid Application Development

What do you mean by memory mapped i/o, What do you mean by memory mapped I/...

What do you mean by memory mapped I/O? In Memory mapped I/O, there is no particular input or output instructions. The CPU can manipulate I/O data residing in interface register

What is race around condition, What is race around condition? Ans: ...

What is race around condition? Ans: Race Around Condition:- Jn Kn Q(n+1) output   0 1 0 1   0 0

What is linear bounded automation, What is linear bounded automation?  ...

What is linear bounded automation?   A linear bounded automation is restricted type of Turing machine where in the tape head isn't permitted to move off the portion of the tape

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd