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 overlays? To enable a process to be larger than the amount of memory allocated to it, overlays are used. The idea of overlays is to keep in memory only those instructi

Q. How does computer know that overflow has happened? Illustration: Add numbers 65 and 75 in 8 bit register in signed 2's complement notation.  Here expected result is

Bitwise Operators Like  other  operators  bitwise  operators  have  rules  of  precedence  and  associativity  that determine how expressions involved them are evaluated.

How does the Xml Serializer work?  What ACL permissions does a process using it require?   Xml Serializer needs write permission to the system's TEMP directory.

A Header in CGI document can represent? A header into CGI document can show format of the document and the location if document used to various URL.

In a particular exchange during busy hour 1200 calls were offered to a group of trunks, during this time 6 calls were lost. The average call duration being 3 minutes Calculate Tr

An object model for university system Establishing relationship among various classes in the system is the primary activity. Here, we have a simple model of a University System

a) Give eight properties for each of static RAM (SRAM) and DRAM (dynamic RAM) and provide the low-level structure of each type of memory. b) Assume a system with 16 Megabytes o

Locality of reference implies that the page reference being made by a process is Ans. Locality of reference means that the page reference being made through a process is proba

CIH, also known  as Chernobyl or Spacefiller, is a Microsoft Windows computer virus which first emerged in 1998. It is one of the most damaging viruses, overwriting critical inform