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

Determine the performance of a parallel algorithm, Q. Determine the perform...

Q. Determine the performance of a parallel algorithm? One more method of determining the performance of a parallel algorithm can be performed after calculating a parameter know

Characteristics of input- output channels, Q. Characteristics of input- out...

Q. Characteristics of input- output channels? The I/O channel represents an extension of DMA concept. An I/O channel has ability to execute I/O instructions that gives complete

The events of an aspx page execute, In what order do the events of an ASPX ...

In what order do the events of an ASPX page execute. As a developer is it important to understand these events?   If you try to access it in Page_Load that is way previous th

What are the properties of electronic cash, What are the properties of elec...

What are the properties of electronic cash? Properties: 1. Monetary Value: Monetary value should be backed by bank certified cashier’s cheque or cash, bank authorized cred

What are font metrics classes, The FontMetrics class is used to describe im...

The FontMetrics class is used to describe implementation-specific properties, like ascent and descent, of a Font object.

Define multiprogramming, Define Multiprogramming. Multiprogramming: ...

Define Multiprogramming. Multiprogramming: A multiprogramming operating system is system which allows extra than one active user program or part of user program to be store

Distinguish between combinational & sequential logic circuit, Distinguish b...

Distinguish between combinational logic circuits and sequential logic circuits. Ans: Combinational logic circuits:- (i) Outputs only depend upon present state of the i

Evaluate 23 - 48 using the 2's complement method, Perform the 23 - 48 opera...

Perform the 23 - 48 operations using the 2's complement method. Ans. Given 23 - 48 firstly add them       23                         0 1 0 1 1 1 - (- 48)                     +

Performance of pipelines with stalls, Performance of Pipelines with Stalls:...

Performance of Pipelines with Stalls: A stall is reason of the pipeline performance to degrade the ideal performance.                                             Average in

Branch (control) hazards in computer architecture, Branch (control) hazards...

Branch (control) hazards in computer architecture : Branching hazards (also called control hazards) take place when the processor is told to branch -for example, if a defin

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