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
Problem : (a) State and describe the transmission ranges associated with wireless transmission. Illustrate your answer with a diagram. (b) Sketch a graph representing how a

An HTML document can be created by using any HTML editor or text editor such as notepad etc. STEPS FOR CREATING A SIMPLE HTMLPROGRAM   1. Go to Start -> Programs->A

Q. Define about Hyper-threading technology? Hyper-threading technology enables a single microprocessor to behave as two separate threaded processors to operating system and app

Explain Garbage collection In this method two passes are made over the memory to identify new areas. In the first pass it traverses all pointers pointing to allocated areas an

What are the functions of virtual file system (VFS)? a. It splits file-system-generic operations from their implementation explaining a clean VFS interface. It allows transpare

How  do  I  prevent  selected  parameters  of  a  module  from  being  overridden  during instantiation? If a specific parameter within a module must be prevented from being ov

Random Search - artificial intelligence: Some problems to be solved by a search agent are more creative in nature, for example, like in writing poetry. In this case, it is oft

Explain any three policies for process scheduling that uses resource consumption information. All three policies for process scheduling are explained below in brief: 1. Fi

What are the two levels in defining a Match Code? Match Code Object. Match Code Id.

A logic gate is an electronic circuit that generates a typical output signal which depends on its input signal. Output signal of a gate is a general boolean operation of its input