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

Brief explanation of all elements in activity diagrams, ? Activities: An ac...

? Activities: An activity shows an action that performed in the system. ? Transitions: Transitions are shown by open arrow heads. Transitions are used to specify the flow among

What are the benefits of electronic data interchange process, What are the ...

What are the benefits of electronic data interchange process? Advantages of Electronic Data Interchange: a. EDI replaces paper transactions along with electronic transac

Advantages of using clusters, Q. Advantages of using clusters? Para...

Q. Advantages of using clusters? Parallel and distributed applications Decreased turnaround time Balanced loads Utilization of more powerful hosts Access to

Addition NO-SIGNS to the Write statement, Suppressing the number signs (+/-...

Suppressing the number signs (+/-) is carried out using the addition NO-SIGNS to the Write statement. Statement is false.

Explain call by value and call by reference, Call by value and Call by refe...

Call by value and Call by reference Call by value means sending the values of the arguments- The value of each of the original arguments in the calling function is copied in

Water chemistry, Discuss the problem when a boiler is fed with lime-soda so...

Discuss the problem when a boiler is fed with lime-soda softened water

Where do you set automatic correlation options, Automatic correlation from ...

Automatic correlation from web point of sight can be set in recording options and correlation tab. Here we can enable correlation for the whole script and choose either issue onlin

Software aspects - computer technology , Software Aspects: Software is...

Software Aspects: Software is a generic term covering the concepts, procedures and instructions which enable computer systems to do useful things. Usually, software is conceiv

Why is xml such an important development, It takes away two constraints whi...

It takes away two constraints which were holding back Web developments: 1. Dependence on a one, inflexible document type (HTML) which was being much abused for tasks it was neve

Multithreaded architecture, Q. Multithreaded Architecture? It is clear ...

Q. Multithreaded Architecture? It is clear at the moment if we provide a lot of contexts to multiple threads then processors with numerous contexts are known as multithreaded s

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