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

Design a circuit which computes the square of a number, Design a circuit wh...

Design a circuit which computes the square of a number? This should not make use of any multiplier circuits. This should use Multiplexers and some other logic as: 1^2=0+1=1

Why pointer variable to a function as an argument, Why pointer variable som...

Why pointer variable sometimes desirable to pass a pointer to a function as an argument? Frequently, a called function needs to make changes to objects declared in the calling

What are the basic components of an expert system, Q. What are the basic co...

Q. What are the basic components of an expert system? ANSWER: There are three components of components: Information, people, and IT components. Information kinds are domain exp

Explain the term - restating the requirements, Restating the Requirements ...

Restating the Requirements To have clarity of analytical model of system you must state requirements specific performance constraints with optimization criteria in one documen

Software estimation, Software Estimation The statement of scope helps t...

Software Estimation The statement of scope helps the planner to established estimates using one or more method which fail into two wide categories: empirical modeling and decom

Where does the cpu enhanced mode originate , Intel's 8086 was the first 32-...

Intel's 8086 was the first 32-bit processor, and as the company had to backward-support the 8086. All the modern Intel-based processors will run in the Enhanced mode, capable of sw

Addressing mode, the 68000 has rich of addressing mode . it concerned with ...

the 68000 has rich of addressing mode . it concerned with the way data is accessed . identify the destion addressing mode for EXG D0, A2

Which of the memory is volatile memory, Which of the memory is volatile mem...

Which of the memory is volatile memory ? Ans. A volatile memory is RAM. Term Volatile memory implies the contents of the RAM get erased as soon as the power goes off.

Determine the implementation of jit inventory system, Discuss in detail the...

Discuss in detail the features, benefits and implementation of JIT inventory system. JIT - Just in Time inventory systems - meaning, origin, need for JIT, benefits, Use of JIT

State in brief about polymorphism, State in brief about Polymorphism C...

State in brief about Polymorphism Class hierarchy is the deciding feature in the case of more than one implementation of properties. An object oriented program to compute the

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