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

Write a small program using floating-point operations, Question: a) Wri...

Question: a) Write a small program using floating-point operations in Reverse Polish Notation to evaluate the following: Volume of Sphere = (4/3)πr 3 Consider that the u

What are the functions of virtual file system, What are the functions of vi...

What are the functions of virtual file system (VFS)? a. It splits file-system-generic operations from their implementation explaining a clean VFS interface. It allows transpare

What is reducibility, What is reducibility?  The primary method of prov...

What is reducibility?  The primary method of proving some problems are computationally unsolvable.       It is known as reducibility. Reducibility always includes two problems

What is the necessity of an interface, What is the necessity of an interfac...

What is the necessity of an interface?  Any device that has to be linked to a CPU requires an interface. This takes care of the mismatch in speed, data and electrical character

Show the properties of frame tag, Q. Show the properties of Frame Tag? ...

Q. Show the properties of Frame Tag? This tag is used for placing an HTML file in the frame created. We should now tell browser what to put in every frame.

Explain criteria for choosing type of file organization, What criteria shou...

What criteria should be adopted for choosing type of file organization. Selecting a file organization is a design decision; therefore it must be done having in mind the achieve

Association and classes betwnn student and university, Association and clas...

Association and classes betwnn student and university Association and classes are alike in the sense that classes describe objects, and association describe links. Figure shows

What is post in terms of bios, For the one who still has no idea about the ...

For the one who still has no idea about the BIOS on your PC, notice when you first turn on your PC or laptop a few screens pop up. It may be a logo such as DELL or HP or ASUS, Tyan

What are different types of log records, What are different types of Log re...

What are different types of Log records? V1 and V2.  V1 must be processed before V2.  But, we can have more than single V2 logs

Super ASCII string checker, In the Byteland country a string "s" is said to...

In the Byteland country a string "s" is said to super ascii string if and only if count of each charecter in the string is equal to its ascci value in the byteland country ascii co

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