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
Design a 1-bit full adder: Verify your design Use the 1-bit full adder to build a 4-bit adder with Ci=0 Verify: 1 + 4, and 9 + 9 Sram design: Cell: p - 0.5/0.045;

Q. Explain Redundant Array of Independent Disks levels? One such industrial standard that exists for multiple-disk database schemes is called as RAID which implies Redundant Ar

An ActiveX control has four types of properties: 1. Stock:-> These are standard properties supplied to each control, such as font / color. The developer must activate stock pro

Artificial Intelligence Agents: We introduced what we'll be conversation about in Artificial Intelligence and why those things are necessary. This discussion is of course abou

what is java?

Explain in detail about the Random Scan Display   This device using CRT directs the electron beam only to the parts of the screen where a picture is to be drawn. This kind of d

The digital circuits that we use now-a-days are constructed with NOR or NAND gates in place of AND-OR-NOT gates. NOR & NAND gates are known as Universal Gates as we can realize any

Determine about the Information centres Airports, supermarkets and any application where information needs to be relayed to customers, gain advantage from having automatic inf

The disadvantages of specifying parameter assignments using defparam are: -  Parameter  is  essentially specified  by  the  scope  of  hierarchies  underneath  which  it exists

Global and Local Variables Global variables: The features are as pursue Declared outside of all functions or before main. These can be used in all the functions in the progra