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
Write about TSR TPA also holds TSR (terminate and stay resident) programs which remain in memory in an active state until activated by a hot-key sequence or another event like

How is a Microsoft CRM Workflow tool enabled? A Microsoft CRM Workflow tool enables certainly one to as given below: • Explain business policies based upon established proce

The do while Loop This is very similar to the while loop except that the test occurs at the end of the loop body. This guarantees that the loop is executed at least once before

ascii code add=2unit,replace=1unit,delete=3unit.convert ascii code in minimum cost

Object Oriented Programming 1. Describe that in how many ways the Data can be passed to functions? Explain with the help of one example. 2. Describe how you create class a

What is dynamic random access memory Computer memory today comprises mainly of dynamic random access memory (DRAM) chips which have been built into multi-chip modules that are

State the term Availability - organisational security scheme What data needs to be available continually, compared to data which can be "off line" for limited periods. Th

The 68HC11 series is based on the Motorola 6800/1 programming instruction set and hence is a fairly simple 8 bit microprocessor. The internal structure of the 6800/1 is shown below

The information in ROM is stored ? Ans. By the manufacturer throughout fabrication of the device.

Q. Instruction of a micro-program? A micro-instruction is an instruction of a micro-program. It specifies one or more than one micro-operations that can be executed concurrentl