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

Uml, what is uml ?

what is uml ?

Analyse the website design, Briefly analyse and compare the two website des...

Briefly analyse and compare the two website designs, applying in turn each of the six design principles. This will result in six brief paragraphs. As part of each analysis, expl

C, solution for oadovan string inc language

solution for oadovan string inc language

Workday versus oracle, Workday has set the stage to revolutionize the way c...

Workday has set the stage to revolutionize the way companies manage and facilitatevarious aspects of their business operationsby utilizing cutting-edge cloud-based technologies in

Explain the differences between logical and physical address, Explain the d...

Explain the differences between Logical and physical address space Logical Vs physical address space (1) An address produced by the CPU is commonly referred to like a logica

What are links and associations, What are links and associations? Link ...

What are links and associations? Link is a physical or conceptual connection between objects. A link is an instance of an association.  Association is a explanation of group

What is cursor, What is Cursor? Cursor is a database object used by app...

What is Cursor? Cursor is a database object used by applications to manipulate data in a set on a row-by- row basis, instead of the typical SQL commands that operate on all the

What is the dissimilarity between a lens and a mirror, Q. What is the dissi...

Q. What is the dissimilarity between a lens and a mirror? Answer:- A mirror is a reflective surface that light passes through the glass and hits the silver backing reflect

Explain cause effect graphing, Explain cause effect graphing . Cause-ef...

Explain cause effect graphing . Cause-effect graphing is a test case design method that gives a concise representation of logical conditions and corresponding actions.  The

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