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 are escape sequences characters? List any six of them.  The characters which when used with output functions like printf( ),putc(),put() etc. helps in formatting the outpu

What is dynpro?What are its components ? A dynpro (Dynamic Program) having of a screen and its flow logic and controls exactly single dialog steps. The dissimilar components

Find the Nyquist rate for the following signals: (a) x(t) = 5 sin 3000πt cos 4000πt (b) A binary channel with bit rate 36000 bps is available for PCM voice transmission. Fi

Virtual Manufacturing System Virtual manufacturing system or VMS is a synthetic, integrated manufacturing environment, developed by using information technology tools, exercise

What is Reflection?  It extends the benefits of metadata by permitting developers to inspect and use it at runtime. For example, dynamically verify all the classes contained in

TRANSFORMATION - THE PROCESS OF CHANGE Much of contemporary art and design practice and indeed popular culture is dedicated to looking at how change affects us as individuals a

To avoid race condition, the maximum number of processes that may be simultaneously inside the critical section is The maximum number of processes is one to ignore race conditi

A NN Representation ANNs are skilled on AI lessons because of their inspiration from brain studies and the truth that they are applied in an AI jobs, namely machine learning.

The PVM system supports functional and data decomposition model of parallel programming. It attaches with C, C++, and FORTRAN. The C and C++ language bindings for the PVM user inte

The grade of service is measured in (A) Percentage                                  (B)  Number (C)  Fractional Number                    (D)  Logarithmic Number  Ans