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 SIMD? Single Instruction stream, Multiple Data stream (SIMD) shows an organization that contains many processing units under the supervision of a common control unit. A

Write an assembly program to simulate a microwave

MS Access provides a vast range of functions some of them are ? It is used by small business, departments of large corporations, and by amateurs to make applications on their d

Data Warehousing 1.  With necessary diagram, Describe about Data Warehouse Development Life Cycle. 2. Elucidate Metadata and what is its use in Data Warehouse Architecture?

What is a macro ? How it is defined ? Preprocessor' is a translation phase that is applied to  source code before the compiler  proper  gets  its  hands on  it.  Generally,  th

Define memory cycle time? It is the time delay needed between the initiations of two successive memory operations. Eg. The time among two successive read operations.


Drawbacks to having call centres overseas -  Culture and language problems -  Animosity to overseas call centres (resulting in loss of customers) -  need for extensive r

Q. What is Metropolitan Area Network? Metropolitan Area Network (MAN):  It is privately or public owned communication system that naturally covers a complete city. Speed is abo

Define exception. The term exception is used to transfer to any event that causes an interruption