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

Define the object orientation and its analysis, Object Orientation and Anal...

Object Orientation and Analysis An Object is anything that exists within the problem domain that can be recognized by data and/or behaviour. An example of an object is a bike.

Explain 32 to 1 multiplexer tree, Why is Multiplexer Tree needed? Draw ...

Why is Multiplexer Tree needed? Draw the block diagram of a 32:1 Multiplexer Tree and explain how input is directed to the output in this system. Ans. One of the possible

Write an html program segment that contains hypertext links, Write an HTML ...

Write an HTML program segment that contains hypertext links from one document to another . HTML permits any item to be placed as a hypertext reference. Therefore a single word

What are the various design constraints, What are the various Design constr...

What are the various Design constraints used while performing Synthesis for a design? 1. Make the clocks (frequency, duty-cycle). 2. Explain the transition-time requirements

Web services method, Why cant datareader be returned from a Web Services Me...

Why cant datareader be returned from a Web Services Method? Ans) Because datareader is not serializable.

Analysis of algorithms, Analysis of Algorithms For this task, each stu...

Analysis of Algorithms For this task, each student should do two things: An empirical analysis of the runtime and comparisons made for all algorithms as a function of input si

Explain inheritance, Can you explain what inheritance is and an example of ...

Can you explain what inheritance is and an example of when you might use it? The process of deriving a new class from an existing class is known as Inheritance. The old class i

write a ''c'' program to accept any 3 digit integer number, Write a 'C' pr...

Write a 'C' program to accept any 3 digit integer number from the keyboard and display the word equivalent representation of the given number

When can a user program execution be interrupted, When can a user program e...

When can a user program execution be interrupted? It won't be desirable to interrupt a program when an instruction is being executed and is in a state such as instruction decod

What is drawbacks of cd- rom, Q. What is Drawbacks of CD- ROM? Drawbac...

Q. What is Drawbacks of CD- ROM? Drawbacks of CD- ROM are as below: 1. It is read-only and can't be updated. 2. It has an access time much longer than magnetic disk dri

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