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

Logical representations, Logical Representations: If all human beings ...

Logical Representations: If all human beings spoke the same language, there would be a much more less misunderstanding in the world. The problem regarding with software engine

Give example of stack using encapsulation of OOA, Give example of stack usi...

Give example of stack using encapsulation of OOA An example of the Stack.  A Stack abstraction provides methods like pop (), push (), isEmpty(), isFull(). The Stack can be i

Participate in grid computing, Different systems that can participate in gr...

Different systems that can participate in grid computing as platform are:  Windows 3.1, 95/98, NT, 2000 XP , DOS, OS/2, , supported by  Intel ( x86); Mac OS  A/UX (Unix)  sup

Explain the handshaking signals, a. Explain the hardware mechanism for hand...

a. Explain the hardware mechanism for handling multiple interrupt requests. b. What are handshaking signals? Describe the handshake control of data transfer during input and out

Principles for developing successful system, Q. Principles for developing s...

Q. Principles for developing successful system? (1)  Both developers and customers must be involved for accuracy in the information. (2)  A problem solving approach must be

How to add a wait state when creating a verification point, 1. Start to mak...

1. Start to make the verification point. 2. In the confirmation Point Name dialog box, select Apply wait state to confirmation point. 3. Type values for the following option

Illustrate the working of encoders, Q. Illustrate the working of Encoders? ...

Q. Illustrate the working of Encoders? An Encoder performs reverse function of decoder. An encoder has 2n input lines and 'n' output line. Let's see 8 ×3 encoder that encodes 8

Explain in detail about the dynamic timing, Explain in detail about the Dyn...

Explain in detail about the Dynamic timing a. Design is simulated in full timing mode. b. Not all possibilities tested, as it is dependent on input test vectors. c. Simul

Data warehouse, 1) Define a job scheduling strategy that will meet business...

1) Define a job scheduling strategy that will meet business requirement of reporting availability by 6am CST for the following cubes? Show the job scheduling dependencies in a pict

How physical addressing is performed in wan, How physical addressing is per...

How physical addressing is performed in WAN?  WAN networks operate as similar to a LAN. All WAN technology describes the specific frame format a computer uses while sending an

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