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

How free-space is managed using bit vector implementation, How free-space i...

How free-space is managed using bit vector implementation? The free-space list is executed as a bit map or bit vector. Each block is shown by 1 bit. If the block is free, the b

Connectivity options accessible to internet subscribers, What are the diffe...

What are the different connectivity options accessible to Internet Subscribers? Explain in detail. Internet Connectivity Options: Internet access is perhaps one of the ma

Explain the terms topology used in lans, Explain the terms topology used in...

Explain the terms topology used in LANs. (i) LAN topologies: This network topology is a physical schematic that shows interconnection of the several users. There are four fun

Explain rational robots coding standards, The standards are for all testers...

The standards are for all testers using the IDE of Rational Robot to make their automated test scripts. The mission is to decrease maintenance costs when it comes to changes.

Explain about the passive graphics device, Explain about the passive graphi...

Explain about the passive graphics device A passive graphics device simply draws pictures under computer control; i.e. it allows the computer to communicate graphically with th

Validate the xml document , As an XML expert you are needed to model a syst...

As an XML expert you are needed to model a system for an online furniture shop. After an interview with the shop manager you have the certain information: The detail of th

Mutation - canonical genetic algorithm, Mutation: However it may appea...

Mutation: However it may appear that the above recombinations are a little arbitrary that especially as points defining whether crossover and inversion occur are chosen random

Define cpu scheduling, Define CPU scheduling. CPU scheduling is the met...

Define CPU scheduling. CPU scheduling is the method of switching the CPU among various processes. CPU scheduling is the basis of multiprogrammed operating systems. By switching

Minimum and maximum algorithm, For this assignment, you will need to create...

For this assignment, you will need to create an ARM assembly language code routine that implements an algorithm to search through an array and find BOTH the minimum and maximum val

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