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

Technology impact on job design - information system, Technology impact on ...

Technology impact on job design - Information System The implementation of technology into work has had a significant impact on the types and content of job that are now avail

Combinational logic circuits, A circuit can be designed to perform manydiff...

A circuit can be designed to perform manydifferent functions e.g.a circuit has 3 inputs A, B and C and 3 outputs:Output X is logic level 1 (or 'high') if one or moreinputs are at l

Illustration of instruction format, Let's provide you a fundamental illustr...

Let's provide you a fundamental illustration by which you may be able to define the concept of instruction format.  Let us consider the instruction format of a MIPS computer. MI

What is .net and .net framework, What is .NET / .NET Framework?  It is ...

What is .NET / .NET Framework?  It is a Framework in which Windows applications might be developed and run. The Microsoft .NET Framework is a platform for building, deploying,

Line of code of assembly language, In how many ways line of code of assembl...

In how many ways line of code of assembly language can be divided? A line of code of an assembly language program can be divided in three columns called as fields. The fields d

Determine the input and output devices, I/O devices need to be matched up t...

I/O devices need to be matched up to computer application. -  Computer-aided design (graph plotters, large screens, etc.) -  Virtual reality (data gloves, data goggles, etc.)

What is the benefit of report wizard over an auto report, What is the benef...

What is the benefit of Report Wizard over an Auto Report? It takes a little more work to make a report with the report wizard than with the Auto Report but you have a lot more

How much duration is required for an off-hook signal, An off-hook signal wi...

An off-hook signal will repeat for a/an                   duration. For a/an finite duration, an off-hook signal will repeat.

State the types of common toes deformities a, Common toes deformities are: ...

Common toes deformities are: 1. Hallux valgus: Deviation of great toe towards the second toe resulting in prominence of first metatarsal head.  Later on there is formation of

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