Binary search, Computer Engineering

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.

Posted Date: 2/23/2013 6:44:24 AM | Location : United States







Related Discussions:- Binary search, Assignment Help, Ask Question on Binary search, Get Answer, Expert's Help, Binary search Discussions

Write discussion on Binary search
Your posts are moderated
Related Questions
What is centralized SPC, what are its modes of operation? In this centralized control, all the control equipment is replaced through a single processor that must be quite power

The Orbix Connect resource adapter is packaged as a standard J2EE Connector Architecture resource adapter archive (RAR) file, corbaconn.rar. The corbaconn.rar file having all the c

Question: (a) Explain how a Mobile Terminating call, from a PSTN phone, is processed in a GSM network. Illustrate your answer with a diagram. (b) Top-Net, a new telecommuni

What are the end-to-end layers of OSI structure? The layers 4 to 7 of ISO-OSI reference model communicate along with peer entities into the end systems. Now here is no communi

Explain all the categories that are served by Common Control switching. Common Control Switching System: It is a functional block diagram of a common control switching system i

Business Narrative Aussie Wine Tours (AWT) conduct tours of the wineries of Victoria's Yarra Valley wine region. The tours take place on the last Sunday of each month. Currentl

What is meant by opening a data file A data file is a file that can be read from or written to. Data files are particularly useful when large amounts of data are involved. Each

What are the properties of electronic cash? Properties: 1. Monetary Value: Monetary value should be backed by bank certified cashier’s cheque or cash, bank authorized cred

Which of the memory is volatile memory ? Ans. A volatile memory is RAM. Term Volatile memory implies the contents of the RAM get erased as soon as the power goes off.

WhT is pollymara