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 100 line exchange with two-motion line finders, Explain 100 line ex...

Explain 100 line exchange with two-motion line finders. Design: In such design, here are 24 line finders. When any of the 100 subscribers has to find access to any of the 24

Propositional inference rules, Propositional Inference Rules: Proposit...

Propositional Inference Rules: Propositional Inference Rules Equivalence rules are mostly useful because of the vice-versa aspect, that means like we can search backwards and

Relational algebra expressions , Write Relational algebra expressions for t...

Write Relational algebra expressions for the given queries. (i) List the employee numbers, employee names and their manager numbers working in several branches who earn more than

What is the working of sound cards, Q. What is the working of Sound cards? ...

Q. What is the working of Sound cards? Multimedia has become a very significant part of today's PC. Home user wants hear songs and watch movies. The Software developer hacking

Define html, HTML is a Hyper text Markup Language and it is  Scripting La...

HTML is a Hyper text Markup Language and it is  Scripting Language

How are interrupt handled by the operating system, How are interrupt hand...

How are interrupt handled by the operating system? The fundamental interrupt mechanism works as follows: The CPU hardware has wire called the interrupt-request line which

What is reducibility, What is reducibility?  The primary method of prov...

What is reducibility?  The primary method of proving some problems are computationally unsolvable.       It is known as reducibility. Reducibility always includes two problems

Defines a macro, Defines a macro Defines a macro with the given name, h...

Defines a macro Defines a macro with the given name, having as its value the given replacement text. After that (for the rest of the current source file), wherever the preproce

Keys, why impotant keys

why impotant keys

What are the various components in sequence diagrams, ? Actor: Actor shows ...

? Actor: Actor shows an external user / end user who interact with the system. ? Object: Object is shown by one of components of the system. ? Unit: A unit is a subsystem, o

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