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

Sap system-wide security settings, You are required to review the system-wi...

You are required to review the system-wide security settings on our SAP system. The data file RSPARAM contains an extract from the client's system. You are to produce a report (

Explain classless inter-domain routing, Explain Classless Inter-Domain Rout...

Explain Classless Inter-Domain Routing. It is a new addressing scheme for the internet that permits for more efficient allocation of IP addresses than old class A, B and C addr

Difference between the std and class module in vb, Std Global within the p...

Std Global within the project.  Class Global throughout the all project only thing is we require to set the type lib. Class Modules can be Instantiated.

What are the major functions of io system, What are the major functions of ...

What are the major functions of IO system?  i. Interface to the CPU and memory by the system bus.  ii. Interface to one or more IO devices by tailored data link.

Explain opening files for reading only in c, Opening Files for Reading Only...

Opening Files for Reading Only     : A data file is a file that you can open and read its contents visually - for example, C source files, .dat files, HTML etc - anything that look

Determine the advantages of bcd adder, Determine the advantages of BCD Adde...

Determine the advantages of BCD Adder Now let us see the arithmetic addition of two decimal digits in the BCD, with a possible carry from previous stage. As each input digit do

Describe about the layered computer design, Describe about the Layered comp...

Describe about the Layered computer design Introduction Layered computer design focuses on computer design. It uses top-down, layered approach to design and also to improve

Explain different parameter passing mechanisms to a function, What are the ...

What are the different parameter passing mechanisms to a function? The different parameter-passing mechanisms are given below: 1.   Call by value 2.   Call by value-resu

Lexical analyser, The aim of this project is for you to construct a fully w...

The aim of this project is for you to construct a fully working compiler for a small simple programming language, SPL. The compiler will read in SPL source code and produce ANSI C

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