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

Give the sequence of procedure calls for server and client, Give the sequen...

Give the sequence of procedure calls for both server and client for connect ion-oriented application.   In connection oriented communication the order of Procedure call

What is an algorithm, What is an algorithm The solution to any problem ...

What is an algorithm The solution to any problem that is stated by an exact number of well-defined procedural steps is known as an algorithm.

What is persistence, What is Persistence When you make an object, it e...

What is Persistence When you make an object, it exists for so long as you need it, but under no circumstances object exist when program terminates. While this makes sense at s

What is normal form, What is normal form? A normal form is a guideline ...

What is normal form? A normal form is a guideline for relational database tables that enhances data consistency. As tables satisfy higher levels of normal forms, they are less

Forward chaining, Forward Chaining: Now we have suppose we have a set ...

Forward Chaining: Now we have suppose we have a set of axioms that we know are true statements about the world. Whether we set these to each be an initial state of the segoal

Explain management information base variables, Explain MIB (Management Info...

Explain MIB (Management Information Base) variables. MIB is a set of named items which an SNMP agent knows. To control or monitor a remote computer, a manager should fetch or s

Differences between cisc and risc architectures, Question: a) What is ...

Question: a) What is the main difference between the Princeton and Harvard microprocessor architectures? b) State five main differences between CISC and RISC architectures?

How the canvas class and the graphics class are linked, A Canvas object giv...

A Canvas object gives access to a Graphics object by its paint() method.

Bernstein conditions for detection of parallelism, Bernstein Conditions for...

Bernstein Conditions for Detection of Parallelism For implementation of instructions or block of instructions in parallel, it should be guaranteed that the instructions are ind

What is recursing downwards, What is recursing downwards? And its ways. ...

What is recursing downwards? And its ways. The design process generally works top-down; you start with the higher level operations and proceed to describe lower level operation

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