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

Scope of expert system, The scope of the experts system is very limite...

The scope of the experts system is very limited. It cannot work outside the field it is being used. The users knowledge is required to adjust to new situation. To reduce

Limitations of experts system, 1. It is hard even for a highly skilled ex...

1. It is hard even for a highly skilled experts to abstract good situational assessment when he is under time pressure. 2. Expert systems perform well with specific t

What is the significance of the screen number ''0'', What is the significan...

What is the significance of the screen number '0'? In "calling mode", the special screen number 0 (LEAVE TO SCREEN 0) causes the system to jump back to the last call level.  Th

Show the dynamic range and colour depth, Q. Show the Dynamic Range and Colo...

Q. Show the Dynamic Range and Colour Depth? Dynamic Range is the number of colours a colour scan or number of grays a monochrome scanner can distinguish. The dynamic range is t

How does computer know that overflow has happened, Q. How does computer kno...

Q. How does computer know that overflow has happened? Illustration: Add numbers 65 and 75 in 8 bit register in signed 2's complement notation.  Here expected result is

Determine the decimal equivalent of hexadecimal number, The hexadecimal num...

The hexadecimal number for (95.5) 10 is ? Ans. (95.5) 10 = (5F.8) 16 Integer part Fractional part 0.5x16=8.0

What are the uses of interactive reporting, What are the uses of interactiv...

What are the uses of interactive reporting? The user can actively control data retrieval and show during the session.  Instead of an extensive and detailed list, you make a ba

What layers are covered under end to end layer connectivity, What layers ar...

What layers are covered under end to end layer connectivity? The layers 4 to 7 of ISO-OSI reference model communicate along with peer entities into the end systems. There is n

Greedy search - artificial intelligence, Greedy Search - artificial intelli...

Greedy Search - artificial intelligence: If we have a heuristic function for states, defined as above, so we can simply measure each state with respect to this measure and ord

Applications of generic framework for electronic commerce, How are the appl...

How are the applications of generic framework for electronic commerce performed? To perform applications, this is essential to have Supporting Information and Organizational In

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