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

Perform multiplication with showing content of accumulator, Perform multipl...

Perform multiplication with showing the contents of accumulator, B register and Y register during each step. (Accumulator, B, Y are 4-bit registers) B=06 Y=02

Computer organisation, How many 32K X 1 RAM chips are needed to provide a m...

How many 32K X 1 RAM chips are needed to provide a memory capacity 256 kilobytes?

Boiler troubles, Differences between internal and external treatment in boi...

Differences between internal and external treatment in boiler

What are the advantages of a smart card, What are the advantages of a Smart...

What are the advantages of a Smart Card? Advantages of Smart Card as given below: a. This provides convenience and assists for multiple currencies over borders. b. Us

Draw and illustrate the block diagram of DMA controller, Draw and illustrat...

Draw and illustrate the block diagram of DMA controller. Also discuss the various modes in which DMAC works. Direct memory access (DMA) is a process in that an external device

Why is catch almost always a bad idea, Why is catch (Exception) almost alwa...

Why is catch (Exception) almost always a bad idea?  Well, if at that point you know that an error has happened, then why not write the proper code to handle that error instead

What is an xml entity, Problem : (a) Show whether or not a standard for...

Problem : (a) Show whether or not a standard format for representing data, such as XML, is needed. (b) Using an appropriate example, describe how data is organized in a dat

forensics capability relevant to a honeynet server, A local government org...

A local government organisation needs to deploy a honey net. To this end you are to deploy a honeynet based on the supplied network diagram (separate download) that should give sop

What are the requirements for a swapper to work, What are the requirements ...

What are the requirements for a swapper to work? The swapper works on the highest scheduling priority. Firstly it will look for any sleeping method, if not found then it will

State the advantages of bespoke software, State the advantages of Bespoke ...

State the advantages of Bespoke Software -  specifically designed for application and hence more efficient and will only contain the features wanted; as it will be devoid 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