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

Combining logic gates - boolean algebra, More complicated logic circuits ca...

More complicated logic circuits can be made byconnecting a number of simple logic gates.How do we decide how to connect the gates togive a particular function e.g. output Y?We need

Pd controller, PD controller Student should aim for Kp and Kd value that...

PD controller Student should aim for Kp and Kd value that will minimize the steady error with improved rise time and settling time. The amount of over shoot should not be more t

How many types of stages include in process of data mining, How many types ...

How many types of stages include in process of data mining? The process of data mining comprised three stages as given below: a) The initial exploration b) Model buildin

Illustrate the state diagrams of dynamic modelling, Dynamic modelling: stat...

Dynamic modelling: state diagrams A state diagrams allow you to further explore operations and attributes which need to be defined for an object. They comprises of sets of sta

What is loader, What is loader? Loader is a system software which havin...

What is loader? Loader is a system software which having a set of utility programs. It will load the object program to the memory.

Explain the basic syntactic constructs through reductions, Recognition of b...

Recognition of basic syntactic constructs through reductions, this task is performed by? By Syntax analysis, recognition of fundamental syntactic constructs through reductions

Define briefly about extranet, Define briefly about Extranet. Extrane...

Define briefly about Extranet. Extranet: Extranet is Extension of an Intranet which makes the latter available to outside companies or individuals along with or without

What is a demultiplexer, What is a Demultiplexer ? Ans. Demultiplex...

What is a Demultiplexer ? Ans. Demultiplexer has similar circuit as decoder but here E is obtained as the particular input line, the output lines are similar as decode

Use string manipulating functions , Write a script that will first initiali...

Write a script that will first initialize a string variable that will kept x and y coordinates of a point in the form 'x 3.1 y 6.4'.  Then, use string manipulating functions to ext

Associative array processing, Consider that a list of record or a table is ...

Consider that a list of record or a table is stored in the memory and you wish to find some information in that particular list. E.g. the list comprises three fields as displayed b

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