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

Show network topology in digital system, Q. Show Network Topology in digita...

Q. Show Network Topology in digital system? This deals with the geometrical arrangement of nodes (endpoints consisting of physical devices such as terminals, printers, PCs, and

Explain conditions for the critical section problem solution, What are the ...

What are the properties which a data item should possess to implement a critical section? The Critical Section Problem Solution should satisfy the following conditions: 1.

Explain about data segment, DATA SEGMENT  NUM1            DB      15h;...

DATA SEGMENT  NUM1            DB      15h;     First number   NUM2            DB      20h;     Second number  RESULT DB?  ; Put sum here  CARRY DB? ; Put any carry he

Signals and systems, Im doing computer engineering in Thailand.. Second yea...

Im doing computer engineering in Thailand.. Second year, and got project regarding sysnal and systems.. I and my team mates have no idea on what should we do.. Could u kindly sugge

Explain binary number system, Explain Binary number system. Ans. Bi...

Explain Binary number system. Ans. Binary Number System The number of system along with base or Radix two is termed as the Binary Number System. To show the number, 0 a

Explain handlers classification, Handlers Classification In 1977, Wolfg...

Handlers Classification In 1977, Wolfgang Handler suggested a complex notation for representing the pipelining and parallelism of computers. Handler's categorization addresses

Describe about instruction set, Q. Describe about Instruction set? Inst...

Q. Describe about Instruction set? Instruction set is the boundary where computer designer and computer programmer see the same computer from various viewpoints. From the desig

Efficiency of vector processing over scalar processing, Efficiency of Vecto...

Efficiency of Vector Processing over Scalar Processing As we know a serial computer processes single scalar operands at a time. So if we have to process a vector of length 'n'

Describe session handling in a web farm, Describe session handling in a web...

Describe session handling in a web farm, how does it work and what are the limits ?   In ASP.NET there are three ways to handle session objects. Single support the in-proc mec

Explain three-way handshake mechanism, Explain Three-Way Handshake Mechanis...

Explain Three-Way Handshake Mechanism used by TCP to terminate a Session reliably. Just to guarantee that connection is sets up or terminated reliably, transfer control protoco

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