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 fork and exec system calls, What is the use of fork and ...

What is the use of fork and exec system calls?  Fork is a system call by which a new process is formed. Exec is also a system call, which is used after a fork by one of the two

What is multiprogramming, Multiprogramming is a rapid switching of the CPU ...

Multiprogramming is a rapid switching of the CPU back and forth among processes.

Find out data changing from special code to temporal code, Data can be chan...

Data can be changed from special code to temporal code by using ? Ans. By using Shift Registers data can be changed from special code to temporal code. A Register wherein data ge

the bias and standard error , A random variable (X) is modelled as an expo...

A random variable (X) is modelled as an exponentially distributed with mean 30 units. Simulate N = 50 samples from this distribution, and every sample must have m = 20 simulated va

Characteristics of input- output channels, Q. Characteristics of input- out...

Q. Characteristics of input- output channels? The I/O channel represents an extension of DMA concept. An I/O channel has ability to execute I/O instructions that gives complete

Direct addressing and immediate addressing mode , Direct Addressing and  I...

Direct Addressing and  Immediate Addressing mode - computer architecture:  Immediate Addressing: It is the simplest form of addressing. Here, the operand is itself given

Abap/4 dictionary structures without an underlying database, It is not poss...

It is not possible to use ABAP/4 Dictionary Structures without an underlying database using LDB. True.  You can use additionally related tables, along with the tables explaine

Problems for decision tree learning, A ppropriate Problems for Decision Tr...

A ppropriate Problems for Decision Tree Learning - Artificial intelligence It is a expert job in AI to select accurately the right learning representation for a particular lea

Input-output techniques, After going through details of device interfaces n...

After going through details of device interfaces next point to be discussed is how the interface can be used to support I/O from devices. Binary information received from an extern

Simplify the boolean expression, Simplify the Boolean expression F = C(B + ...

Simplify the Boolean expression F = C(B + C)(A + B + C). Ans. Simplification of the given Boolean Expression F = C (B +C) (A+B+C) given as F = C (B+C) (A+B+C) = CB + CC [(A+B+C

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