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

What is a abap/4 module pool, What is a ABAP/4 module pool? -Every dynp...

What is a ABAP/4 module pool? -Every dynpro refers to exactly one ABAP/4 dialog program. Like a dialog program is also known as a module pool ,since it having on interactive mo

Electrical technology, voltage,current and power relation in a delta connec...

voltage,current and power relation in a delta connection

What is garbage collection and what is it used for, In computer science, ga...

In computer science, garbage collection (GC) is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by

Operator, write algorithm and draw flowchart for exchange the values of two...

write algorithm and draw flowchart for exchange the values of two variables.

Predicate logic - artificial intelligence, Translate the following sentence...

Translate the following sentences into predicate logic, using Russell's theory of definite descriptions to represent the article the. a. The wizzard of Oz fell. b. Everyone a

Page directive include, What is the difference between, page directive incl...

What is the difference between, page directive include, action tag include? Ans) One difference is whereas using the include page directive, in translation time it is making t

What is called network, Network with point-to-point link is known as (...

Network with point-to-point link is known as (A) Fully Connected Network        (B)  Half Connected Network (C)  Duplex Connected Network    (D)  None of these Ans:

Anti reflection coating, expression for thickness and refractive index of c...

expression for thickness and refractive index of coating material to act as anti reflection coating

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