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 compound statement If we wish to have more than one statement following the if or the else, they should be grouped together between curly brackets. Such a grouping is c

APPLICATIONS OF PARALLEL PROCESSING Parallel computing is an development of sequential computing which tries to emulate what has always been the condition of affairs in natural

WHAT IS COMPUTER? Computer is termed in the Oxford dictionary as "An automatic electronic apparatus for making controlling operations or calculations    which are expressible i

What is an operating system? An operating system is system software which provides interface between hardware and user. The operating system gives the means for the proper uti

Objects, messages, class, inheritance and polymorphism are the major concepts of object orientation.

Define bootstrap loader? The ROM portion of main memory is required for storing an initial program known as bootstrap loader. It is a program whose function is to start the com

Uniform Path Cost Search - artificial intelligence: A breadth first search will find the solution with the shortest path length from the initial state to the goal state. In fa

What is asynchronous DRAM? In asynchronous DRAM, the timing of the memory device is controlled asynchronously. A specialized memory controller circuit gives the essential contr

Identify three specific weaknesses in the design of the websites, derived from your analyses within Questions Part (c) and/or Question Part (a). There should be at least one weakne

Overfitted the data: Moreover notice that as time permitting it is worth giving the training algorithm the benefit of the doubt as more as possible. However that is, the error