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

cell array to a spreadsheet, The xlswrite function can write the contents ...

The xlswrite function can write the contents of a cell array to a spreadsheet.  A manufacturer kepts information on the weights of some parts in a cell array.  Every row stores the

Logic gates required to build a half adder, What are the gates required to ...

What are the gates required to build a half adder ? Ans. The gates needed to build a half adder are EX-OR gate and AND gate as shown below the logic diagram of half adder:

Intelligent systems assignment, This logbook should be used to record decis...

This logbook should be used to record decisions, ideas, work done by your group on this assignment. Each group should keep one logbook, which must be submitted along with your sour

Fully parallel associative processor (fpap), Fully Parallel Associative Pro...

Fully Parallel Associative Processor (FPAP):  This processor accepts the bit parallel memory organisation. FPAP has two type of this associative processor named as: Word Org

Complicated question, Hi I need a help in this question : A telephone sw...

Hi I need a help in this question : A telephone switchboard handles ? calls on average during a rush hour, and the switchboard can at most make k connections per minute. Write a

Introduction to the operating system, Q. Introduction to the Operating Syst...

Q. Introduction to the Operating System? An Operating system is software that creates a relation between the User, Hardware and Software. It is an interface between the all.

Define the term busy hour, Define the term busy hour Busy Hour: Conti...

Define the term busy hour Busy Hour: Continuous 1- hour period lying completely in the time interval concerned, for that the traffic volume or the number of calls attempts is

Operating system, what is batch system?how the disadvantage of batch system...

what is batch system?how the disadvantage of batch system are overcome in multi-programming operating system?also describe how multi-programmed operating system is milestone in dev

Difference between the testing and verification, Difference between the tes...

Difference between the testing and verification. Verification proves conformance with a specification. Testing tries to find cases where the system does not meet its specifi

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