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
A set of techniques that allow executing a program which is not entirely in memory is called ? Ans. virtual memory which allows executing a program that is not entirely in me

For JK flip flop with J=1, K=0, the output after clock pulse will be ? Ans. The output will be 1 after clock pulse.

Summarize the distinction between an external variable definition and an external variable declaration. When we have ''declared'' a variable, we have meant that we have told th

E Brokerage facilitates search & retrieval of Information The success factor of a brokerage is its ability to retain existing clients and to enhance their satisfaction by effec

SPC is used for (A)  Carrying Exchange Control Functions (B)  Carrying Subscriber Control Functions (C)  Exchange Hardware (D)  Signalling Purpose Ans:

Porcess of Identifying Input and Output Values First, recognize what data is going to be used as input to system, and what will be output from system. Input and output values

Explain the term middleware in context of RPC. A variety of commercial tools have been urbanized to assist the programmer in constructing client- server software. These tools a

Q. Connection Machine FORTRAN? Connection Machine Fortran was a subsequent SIMD language developed by Thinking Machines Corporation. Connection Machine Fortran incorporated all

Q. Explain Micro-operations performed by CPU? The micro-operations performed by CPU can be categorized as:    Micro-operations for data transfer from register-memory, re

Name the appliances which are controlled by micro-processor Many household appliances which are microprocessor-controlled do not have operating systems (for example microwave o