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

.bus, clasification of bus

clasification of bus

C++ program on pebble merchant, how to solve pebble merchant problem.? codi...

how to solve pebble merchant problem.? coding for it..!

Explain the state space of search problem, Question: (a) Assume you are...

Question: (a) Assume you are a taxi driver. Your taxi can hold four passengers. Passengers pay a flat fee for a ride to the airport, so your goal is to pick up four passengers

What is middleware net dynamics, NetDynamics Application Server was the pri...

NetDynamics Application Server was the primary Java-based integrated software platform. The product was developed by NetDynamics Inc. As Java became the dominant development langua

When recursion functions are declared inline, Describe what happens when re...

Describe what happens when recursion functions are declared inline? Ans) Inline functions property says whenever it will call; it will copy the whole definition of that functi

Why we use addressing schemes, Q Why we use addressing schemes? An ope...

Q Why we use addressing schemes? An operation code of an instruction tells the operation to be performed. This operation is executed on some data stored in memory or register.

The javascript validation not run on the asp.net, Why The JavaScript Valida...

Why The JavaScript Validation Not Run on the Asp.Net? The Asp.Net Button Is post backed on the server & not yet Submit & when it goes to the server its states is lost so if we

What is synchronous message passing, Q. What is Synchronous message passing...

Q. What is Synchronous message passing? In Synchronous message passing is executed on synchronous communication network.  In that case sender and receiver processes should be

What is the efficient data structure used in rdbms, In RDBMS, what is the e...

In RDBMS, what is the efficient data structure used in the internal storage representation? B+ tree. Because in B+ tree, all the data is kept only in leaf nodes, that makes sea

What is macro-expansion, What is macro-expansion? Macro calls lead to m...

What is macro-expansion? Macro calls lead to macro expansion. Throughout macro expansion, the macro call statement is replaced through a sequence of assembly statements.

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