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

Asp.net mvc over asp.net webforms, What is the greatest benefit of using as...

What is the greatest benefit of using asp.net mvc over asp.net webforms? Ans) It is complex to unit test UI with webforms, where views in mvc can be very simply unit tested.

Analysis of amdahls law, The outcomes of analysis of Amdahl's law are: 1...

The outcomes of analysis of Amdahl's law are: 1) To optimize the performance of parallel computers, modified compilers need to be developed which should aim to decrease the numb

Criteria for selecting a theme for a project, Q. Criteria for selecting a t...

Q. Criteria for selecting a theme for a project? Topics for projects as we indicated earlier should emerge from the children's world. Teaching often becomes boring and unintere

Explain usenet and newsgroups, Q. Explain Usenet and Newsgroups? In Int...

Q. Explain Usenet and Newsgroups? In Internet there exists another way to meet people and share information. One such way is through Usenet newsgroups. These are special groups

Use of intrinsic functions in fortran, Q. Use of Intrinsic Functions in FOR...

Q. Use of Intrinsic Functions in FORTRAN? HPF initiates some new intrinsic functions also to those defined in F90. The two mainly often used in parallel programming are system

How cloud can be used in event schedules, How cloud can be used in Event Sc...

How cloud can be used in Event Schedules and Management with an example. Web-based calendars can be used to post dates and schedules for specific public events, such as school

Explain frequency division multiplexing, Explain FDM and show how CCITT sta...

Explain FDM and show how CCITT standards help in building the base band? Frequency Division Multiplexing: This is the process of combining some information channels through s

Software engineering, What are coupling and cohesion and why are they impor...

What are coupling and cohesion and why are they important concepts in software design?

Computer based accounting systems, For the purposes of this assignment, you...

For the purposes of this assignment, you are the accountant for an industrial property development company, Devprop Leasing Co., that typically develops warehouse and industrial 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