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

Simulate a real life product development , The goal is to simulate a real l...

The goal is to simulate a real life product development and familiarize learners with the design process of a system, component, or process to meet desired requires within realisti

What is a modem, What is a Modem? Modems are fundamentally used to int...

What is a Modem? Modems are fundamentally used to interface digital circuits to transmit information on analogue channels as telephone systems. Modem is from modulator-demodul

Define password methods and biometric systems, Define the password methods ...

Define the password methods and Biometric systems for implementing client server network security. In cyberspace, buyers and sellers cannot notice each other. Also within video

The constructed datatype of c, The constructed datatype of C is known as ...

The constructed datatype of C is known as Structure is a constructed datatype of C.

Show the decimal representation in computers, Binary number system is most ...

Binary number system is most common for computer due to two stable states of its components. However unfortunately this isn't a very natural system for us as we deal with decimal n

We cannot use append structures why, If a table that is to be extended cont...

If a table that is to be extended contains a long field, we cannot use append structures why? Long fields in a table must always be located in the last, as the last field of th

How to fix an asic-based design from easiest to most extreme, How to fix an...

How to fix an ASIC-based design from easiest to most extreme? There are different ways to fix an ASIC-based design as given below: Initially, assume some reviews fundamentally.

Estimate the circuit switched network, a) Total available bandwidth = 1 Mbp...

a) Total available bandwidth = 1 Mbps = 1000 Kbps Each user requires send data at the rate of = 500 kbps As it is circuit switched network we have to dedicate the bandwidth So the

Potential of parallelism-parallel computing, Potential of Parallelism P...

Potential of Parallelism Problems in the actual world differ in respect of the degree of natural parallelism inherent in the personal problem domain. Some problems may be simpl

What does realized mean, Realized mean that the component has been painted ...

Realized mean that the component has been painted on screen or that is prepared to be painted. Realization can take place by invoking any of these methods. setVisible(true), show()

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