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

Binary number system using 8 bit registers, Q. Binary number system using 8...

Q. Binary number system using 8 bit registers? Add 25 and -30 in binary number system using 8 bit registers using: Signed magnitude representation Signed 1's comple

Define structural classification, Structural Classification Flynn's cla...

Structural Classification Flynn's classification explains the behavioural idea and doesn't take concern into the computer's structure. Parallel computers can be categorized bas

Explain that lost acknowledgement in packet retransmission, Explain that th...

Explain that the lost acknowledgement does not necessarily enforce retransmission of the packet . To guarantee reliable transfer, protocols utilize positive acknowledgement al

Define software is in machine language or not, Define Software is in machin...

Define Software is in machine language or not Software is in machine language, today it is often developed by first writing in a high-level language or an assembly language or

What is parallel sections construct, What is Parallel Sections Construct? ...

What is Parallel Sections Construct? The parallel sections construct is a shortcut for specifying a parallel construct comprising one sections construct however no other statem

What is managed bean or mbean, A managed bean - sometimes simply referred t...

A managed bean - sometimes simply referred to as an MBean - is a type of JavaBean, developed with dependency injection. Managed Beans are particularly used in the Java Management E

calculates the area and perimeter of a rectangle, Write a program, using f...

Write a program, using functions, that calculates the area and perimeter of a rectangle whose dimensions (Length & width) are given by a user.

What is register set, What is Register Set Register Set:  Register set ...

What is Register Set Register Set:  Register set is used to keep immediate data during the implementation of instruction. This area of processor having of various registers.

Illustrate edge-triggered flip-flops, Q. Illustrate Edge-Triggered flip-flo...

Q. Illustrate Edge-Triggered flip-flops ? Edge-triggered flip-flop is used to synchronize state change at the time of a clock pulse transition in place of constant level. A num

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