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

What is the use of boot block, What is the use of boot block? For a com...

What is the use of boot block? For a computer to start running when powered up or rebooted it needs to have an initial program to run. This bootstrap program tends to be simple

Write a cgi program that keeps a list of computers, Write a CGI program tha...

Write a CGI program that keeps a list of computers that have contacted the server. If comp1 is contacting first time it will display the message: "This is the first contact fr

What is commitment unit, What is commitment unit? When out-of-order exe...

What is commitment unit? When out-of-order execution is permitted, a special control unit is required to guarantee in-order commitment. This is known as the commitment unit. It

Logical representations, Logical Representations: If all human beings ...

Logical Representations: If all human beings spoke the same language, there would be a much more less misunderstanding in the world. The problem regarding with software engine

In 8085 which is called as high order / low order register, Flag is known a...

Flag is known as Low order register & Accumulator is known as High order Register.

Insert images in dreamweaver, Q. Insert images in Dreamweaver? You will...

Q. Insert images in Dreamweaver? You will learn two methods to insert images in Dreamweaver-using Dreamweaver's main menu and using Objects panel. 1. Click anywhere in the l

Explain the term electronic data interchange (edi), Explain the term Electr...

Explain the term Electronic Data Interchange (EDI). Electronic Data Interchange (EDI) may be generally easy to understand as the replacement of paper-based purchase orders alon

What is an interpreted languages, What is an interpreted languages In ...

What is an interpreted languages In interpreted languages, the instructions are implemented immediately after parsing. Both tasks are done by the interpreter. The code is sav

Final project, I need help coming with an idea for BSCE final project, whic...

I need help coming with an idea for BSCE final project, which is solvable in about a semester

Why is xml such an important development, It takes away two constraints whi...

It takes away two constraints which were holding back Web developments: 1. Dependence on a one, inflexible document type (HTML) which was being much abused for tasks it was neve

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