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
Question: (a) Identify the four main enhancements brought along by TKIP on WPA to solve the problems in WEP. (b) The term WarDriving has been frequently used while talking


What are the various layers of a file system? The file system is composed of lots of dissimilar levels. Each level in the design uses the characteristic of the lower levels to

Define the difference between static RAM and dynamic RAM? The RAM family comprises two important memory devices that are static RAM (SRAM) and dynamic RAM (DRAM). The main diff

Assignment 3.b: Experiment with Neural Network Background: In this assignment, you will experiment with neural network for solving different types of practical problems. Y

You can't plan only for the present phase of the project as your future activities are still coarse granular. To have good planning you require to have fine granularity w.r.t the t

Difference between blocking and non-blocking Verilog  language  has  two  forms  of  the  procedural  assignment  statement:  blocking  and  nonblocking. The two are distinguis

Program: A good illustration of code conversion: Write a program to convert a; 4-digit BCD number into its binary equivalent. BCD number is stored as a; word in memory location kno

What are the Advantages of store program control (I) Easy to maintain (II) Easy to control (III) Wide range of services can be provided to customers (IV) Flexible

Fifth Generation (1984-1990) The advancement of the next generation of computer systems is characterized majorly by the acceptance of parallel processing.  Until this time para