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

What is drop-down list, A dialog box such as a File menu that have one comm...

A dialog box such as a File menu that have one command until it is clicked when a number of dissimilar commands "drop-down."

Determine the output of SR flip flop when S=1 and R=0, The output of SR fli...

The output of SR flip flop when S=1, R=0 is ? Ans. When for the SR flip-flop S=set i/p R=reset i/p, as S=1, R=0, Flip-flop will be set means output will be one.

What is structured programming, What is structured programming? Structu...

What is structured programming? Structured Programming: means the collection of principles and practices that are directed toward developing right programs which are simple to

Explain high performance of instruction execution, Q. Explain High performa...

Q. Explain High performance of Instruction execution? High performance of Instruction execution: While mapping of HLL to machine instruction the compiler favours relatively sim

Write-allocate and no-write-allocate policy in a cache, (a) How does a da...

(a) How does a data cache take advantage of spatial locality? Give an suitable example. (b) What are the basic differences between a write-allocate and no-write-allocate po

Spmd model for programming, Q. SPMD model for programming? A normal ass...

Q. SPMD model for programming? A normal assumption was that it must be possible and not too hard to capture the SPMD model for programming MIMD computers in data parallel langu

How does tcp achieve reliability, How does TCP achieve reliability? One...

How does TCP achieve reliability? One of the most significant technologies is retransmission. While TCP stands data the sender compensates for packet loss through implementing

Explain about interrupt-processing sequence, Q. Explain about Interrupt-Pro...

Q. Explain about Interrupt-Processing Sequence? The occurrence of an interrupt fires a numbers of events both in processor hardware and software. Figure below displays a sequen

Distributed network architecture, Problem a) Distributed network archi...

Problem a) Distributed network architecture is whereby services are executed and distributed  among various computers. Give two advantages and two disadvantages of the distrib

Drawbacks to having call centres overseas, Drawbacks to having call centres...

Drawbacks to having call centres overseas -  Culture and language problems -  Animosity to overseas call centres (resulting in loss of customers) -  need for extensive r

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