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

How e-commerce website works, Procedure The only difference between e-...

Procedure The only difference between e-commerce and conventional commerce is that goods in e-commerce are purchased over the internet using a credit card. Also buying and sel

Explain the matlab working environment, This is the set of tools and facili...

This is the set of tools and facilities that you work with as the MATLAB user or programmer. It contains facilities for managing the variables in your workspace and importing and e

What are the digital certificates of hardware computations, What are the Di...

What are the Digital certificates of hardware computations Digital certificates are highly dependent on hardware computations, it is essential that mechanisms are evolved to i

Develop a plan to apply theory of constraints, 1. The Goal: Do you think th...

1. The Goal: Do you think that this is an operational methodology or a philosophy? Please explain. 2. How to apply Constraint Management to a Production Facility? How about to a

What is memory mapped i/o, What is memory mapped I/O? When the I/O devi...

What is memory mapped I/O? When the I/O devices share the similar address space, the arrangement is known as memory mapped I/O.

Super ASCII string checker, In the Byteland country a string "s" is said to...

In the Byteland country a string "s" is said to super ascii string if and only if count of each charecter in the string is equal to its ascci value in the byteland country ascii co

What is public key cryptography, What is Public Key Cryptography Publi...

What is Public Key Cryptography Public-key cryptography is a form of modern cryptography which permits users to communicate safely without lastly agreeing on a shared secret

Explain the working of a binary counter, In binary counter the flip flop of...

In binary counter the flip flop of lowest order position is complemented with each pulse. This means that JK input position must be maintained with logic one

Maximum number of nodes in a binary tree, The maximum number of nodes in a ...

The maximum number of nodes in a binary tree of depth 5 is 31 is the maximum number of nodes in a binary tree

Example of asymptotic notations, Q. Example of asymptotic notations? Th...

Q. Example of asymptotic notations? The function f (n) belongs to the set  (g(n)) if there exists positive constants c such that for satisfactorily large values of n we have 0

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