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

Compact disk read only memory, Q. What is Compact Disk Read Only Memory? ...

Q. What is Compact Disk Read Only Memory? This technology has evolved out of entertainment electronics market where cassette tapes and long playing records are being replaced b

Define secondary memory, Define secondary memory. This memory holds tho...

Define secondary memory. This memory holds those pages that are not present in main memory. The secondary memory is usually a high speed disk. It is known as the swap evice, an

Reading decision trees, Reading Decision Trees: However we can justifi...

Reading Decision Trees: However we can justified by see that a link between decision tree representations and logical representations that can be exploited to make it easier t

Set up a standard population model structure, Set up a standard population ...

Set up a standard population model structure. The population will begin with 24 people. We do not have actual data to support a birth rate, but we could calculate a reasona

Determine the minimal sum of products for boolean expression, Determine the...

Determine the Minimal sum of products for the Boolean expression? Obtain the minimal sum of products for the Boolean expression f=(1,2,3,7,8,9,10,11,14,15) using Quine-McCluske

Array processing, Array Processing We have seen that for performing vec...

Array Processing We have seen that for performing vector operations, the pipelining concept has been taken. There is another method for vector operations. If we have an array o

2 way staircase switch-truth table logic equation & circuit, A staircase li...

A staircase light is controlled by two switches one at the top of the stairs and another at the bottom of stairs a. Make a truth table for this system. b. Write the lo

Explain quadratic probing with respect to hashing technique, Quadratic prob...

Quadratic probing: In the above case when the first insertion is made the probability of latest element being inserted in a certain position is 1/n    where n is the size of the a

Determine about the intranet server, Determine about the Intranet server ...

Determine about the Intranet server The success or usage of the Intranet server is measured by the number of operations it handles per Unit time. The selection of a good server

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