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

Explain about microsoft access, Microsoft access name has been transformed ...

Microsoft access name has been transformed to Microsoft office access. This software incorporates relational database management system which joins GUI (graphical user interface) w

Interconnection network, Interconnection Network Introduction Th...

Interconnection Network Introduction This unit discusses the types and properties of interconnection networks.  In multiprocessor systems, there are multiple I/O modules

Implementation of a data entry application, Develop and submit an original ...

Develop and submit an original implementation of a data entry application. Identify and declare variables which will hold all data that needs to be entered to fill in the attached

Illustrate the categories of micro computers, Illustrate the categories of ...

Illustrate the categories of micro computers Micro computers are usually categorized into desktop models and laptop models.  They are awfully limited in what they can do when c

Simple instruction formats, Simple instruction formats: RISC uses simpl...

Simple instruction formats: RISC uses simple instruction formats. Usually only one or a few instruction formats are used. In these machines instruction length is fixed and alig

Explain the reference count - free memory areas, Explain the Reference Coun...

Explain the Reference Count The system relates a reference count along with each memory area to point out the number of its active users. This number is incremented while a us

Input output in assembly program, Q. Input output in assembly program? ...

Q. Input output in assembly program? Software interrupt is a call to an Interrupt servicing program situated in the operating system. Generally the input-output routine in 8086

Explain the regular expression and transition diagram, State the relation a...

State the relation among Regular Expression, Transition Diagram and Finite State Machines. By using a simple instance establish your claim.   Answer: For each regular language,

Explain grade of service with reference to telephone traffic, With referenc...

With reference to telephone traffic, explain the terms GOS. GOS: in loss systems, the traffic carried through the network is usually lower than the actual traffic offered to

Data routing functions-network properties, Data Routing Functions The d...

Data Routing Functions The data routing functions are the functions which when implemented  the path among the source and the objective. In dynamic interconnection networks 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