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

Application and function areas - artificial intelligence, Application and F...

Application and Function Areas - artificial intelligence: Individual applications and function often drive "AI" research much more than the long term relative field described

Ring, Ring This is a easy linear array where the end nodes are connecte...

Ring This is a easy linear array where the end nodes are connected.  It is equivalent to a engage with wrap around connections. The data transmit in a ring is normally one dire

What is the difference between swapping and paging, What is the difference ...

What is the difference between Swapping and Paging? Swapping: Entire process is moved from the swap device to the major memory for implementation. Process size must be less t

Structure of 8086 cpu, 8086 microprocessor comprises two independent units:...

8086 microprocessor comprises two independent units:  1.  Bus Interface unit 2.  Execution unit Please refer to Figure below. Figure: The CPU of INTEL 8086 Microp

Group cells in a layout table, Now you will put navigation button cells you...

Now you will put navigation button cells you just created into a single table. Grouping cells into a table enables you to control cell spacing and to easily move the cells as a gro

Is dos a real time os, DOS is not a RTOS (real time Operating system), thou...

DOS is not a RTOS (real time Operating system), though MS DOS can be used with certain APIs to attain the RTOS functionality. For example, the RT Kernel (Real Time Kernel) which ca

What are the steps include constructing a functional model, What are the St...

What are the Steps include constructing a Functional Model Recognize input and output values Build data flow diagrams which shows functional dependencies Explain

#title.sequential circuit, design modulo 12 up synchronous counter using t ...

design modulo 12 up synchronous counter using t flip flop

Embedded software, Embedded Software Intelligent products have becom...

Embedded Software Intelligent products have become commonplace for all consumer and industrial market. Embedded software stays in read only memory and is utilised to control

What are digital signatures and its uses, What are Digital Signatures and i...

What are Digital Signatures and its uses? A digital signature is an electronic quite than a written signature which can be used through someone to authenticate the identity 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