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

Decomposition model of parallel programming, The PVM system supports functi...

The PVM system supports functional and data decomposition model of parallel programming. It attaches with C, C++, and FORTRAN. The C and C++ language bindings for the PVM user inte

Illustrate the term EDI trading patterns, Illustrate the term EDI Trading P...

Illustrate the term EDI Trading Patterns? EDI Trading Patterns are illustrated below: a. Hubs and Spokes: Several of the prime movers into the adoption of Electronic Da

Example to show directory in doc, Q. Example to show directory in doc? ...

Q. Example to show directory in doc? Like a file name, the directory name may also have up to eight alpha-numeric characters. The directory name can also have an extension

Propositional inference rules - artificial intelligence, Propositional Infe...

Propositional Inference Rules -Artificial intelligence : Equivalence rules are specifically useful because of the vice-versa aspect,that means we can discover forwards andbackw

Give the solutions for critical section problem, Give the solutions for cri...

Give the solutions for critical section problem? A solution to the critical section problem must specify the subsequent requirements. (a) Mutual exclusion (b) Progress (c)

Name some of synthesizable and non-synthesizable constructs, Can you list o...

Can you list out some of synthesizable and non-synthesizable constructs? not synthesizable->>>> initial ignored for synthesis. delays  ignored for synthesis. ev

Prepurchase and purchase consummation of consumer mercantile, Differentiate...

Differentiate between Prepurchase and Purchase Consummation of consumer mercantile model. The prepurchase interaction for consumers comprises three activities: Product/ser

Explain microcode and VLSI technology, Q. Explain Microcode and VLSI Techno...

Q. Explain Microcode and VLSI Technology? It is considered that CU of a computer be assembled using two ways; create micro-program which execute micro-instructions or construct

Explain about mmx architecture, Explain about MMX architecture MMX arc...

Explain about MMX architecture MMX architecture introduces new packed data types. Data types are eight packed, consecutive 8-bit bytes; four packed, consecutive 16-bit words;

What is the use of buffer register, What is the use of buffer register? ...

What is the use of buffer register? The buffer register is used to avoid speed mismatch among the I/O device and the processor.

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