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

Logic-based expert systems - artificial intelligence, Logic-based Expert Sy...

Logic-based Expert Systems - Artificial intelligence: Expert systems are agents which are programmed to make decisions about real world situations. They are put together by uti

Give explanation of common channel signalling, Explain Common channel signa...

Explain Common channel signalling. Common channel signalling: Signaling systems connection the variety of transmission systems, switching systems and subscriber equipments, i

What are the server specific middle wares, What are the server specific mid...

What are the server specific middle wares? Server specific middle wares. Their role in e-commerce. Additional features needed by e-commerce server. Middleware is the term of

Software project planning, Software Project Planning In the previous da...

Software Project Planning In the previous days of computing software costs comprised a small % of overall computer based system cost. In order of magnitude error software cost

what is feram?, Ferroelectric RAM is a random-access memory same in constr...

Ferroelectric RAM is a random-access memory same in construction to DRAM but uses a ferroelectric layer rather of a dielectric layer to achieve non-volatility. FeRAM is one of a gr

Cn, What is the basic requirement for establishing VLANs?

What is the basic requirement for establishing VLANs?

Explain parallelism conditions, Parallelism Conditions As discussed ear...

Parallelism Conditions As discussed earlier, parallel computing needs the segments to be executed in parallel should be independent of each other. So before executing paralleli

Using the memory map design an absolute decoding circuit, Using the memory ...

Using the memory map below; design an absolute decoding circuit.   The technique is to spot the differences between the start and stop of each device. The Ram chip has the follow

Explain language processor development tools by diagram, Explain Language ...

Explain Language Processor Development Tools (LPDTs) through schematic diagram. LPDT that is Language processor development tools focuses upon generation of the analysis phase

Characteristics of large register file, Characteristics of large-register-f...

Characteristics of large-register-file and cache organizations Large Register File Cache Hold local variables for almost all functio

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