Binary search, Computer Engineering

Assignment Help:

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.


Related Discussions:- Binary search

Explain about deadlock avoidance, Q. Explain about Deadlock Avoidance? ...

Q. Explain about Deadlock Avoidance? To prevent deadlocks two kinds of techniques are used: 1) Static prevention:  It employs P and V operators in addition to Semaphores to

Matlab, 33.A juice company manufactures one-gallon bottles of three types o...

33.A juice company manufactures one-gallon bottles of three types of juice blends using orange, pineapple, and mango juice. The blends have the following compositions: 1 gallon or

Callable modules of program code within one abap/4 program, How can we crea...

How can we create callable modules of program code within one ABAP/4 program? We can create callable modules by two techniques:- By defining Macros. By creating incl

How putchar function is used within a c program, How putchar function is us...

How putchar function is used within a C Program ? The following program reads each character in the first line of input entered at the terminal's keyboard. It uses putchar to d

Differentiate between validation and simulation, Question 1: a) Name a...

Question 1: a) Name and give a brief description of three Real-Time Systems. b) State three downfalls of Embedded Systems. c) Differentiate between a microprocessor an

Explain 100 line exchange with selector finder, Explain 100 line exchange w...

Explain 100 line exchange with selector finder. Design: In place of 100 two-motion selectors as in the case of Design 3, suppose we consider only 24 two-motion selectors. Whe

Define polling, Define Polling. A Polling process is used to recognize...

Define Polling. A Polling process is used to recognize the highest priority source by software means. In this process there is one common branch address for all interrupts.

Microprocessor, can i get the comparison of microprocessors architecture?

can i get the comparison of microprocessors architecture?

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd