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

Which is most general phase structured grammar, Which is most general phase...

Which is most general phase structured grammar? Context – Sensitive is most common phase structured grammar.

Critical path analysis, Given the information provided in Table 1: ...

Given the information provided in Table 1: Prepare an Activity on the Node (AON) Network Diagram ( I recommend you  use MS Project or any drawing tool); Prepare

Subtraction of 01100-00011 using 2's complement method, Subtraction of 0110...

Subtraction of 01100-00011 using 2's complement method Ans. Firstly 1's complement of 00011 is 11100 and 2's complement is 11100 + 1 = 11101. Thus If a last carry is

What is machine language, What is Machine Language? To write program fo...

What is Machine Language? To write program for a computer we need to specify, directly or indirectly the sequence of machine instructions.  These instructions  inside  computer

What is high level formatting, Q. What is High level formatting? In any...

Q. What is High level formatting? In any disk system the space at some time in use would become discarded and therefore will be free for other application. Operating system ass

Explain logical shift micro-operations, Q. Explain logical shift Micro-oper...

Q. Explain logical shift Micro-operations? In logical shift data entering by serial input to left most or right most flip-flop (which depends on right or left shift operations

What is rom, What is ROM? Read only memory [ROM] is used for storing pr...

What is ROM? Read only memory [ROM] is used for storing programs that are permanently resident in the computer and for tables of constants that do not change in value as the pr

By which all systems are identified, In a LAN network every system is ident...

In a LAN network every system is identified by? In a LAN network all systems are identified through IP Address.

Mips simulator: testing, Your code will be tested using a command script. T...

Your code will be tested using a command script. The script is available on Blackboard in the archive MIPSimTest.zip. It contains a ReadMe file that explains how to run the script

Determine about selective set- logic micro operations, Selective set Th...

Selective set The selective-set operation sets to 1 bits in register A where there can corresponding 1's  in  register  B.  It  does  not  affect  bit  positions  which  have

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