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

Data mining, what is data mining and what is its uses in a industry?

what is data mining and what is its uses in a industry?

Which term is associated with snmp, Which term is associated with SNMP? ...

Which term is associated with SNMP? MIB is related with SNMP.

Features of mpi-1, Features of MPI-1 Binding for FORTRAN and C ...

Features of MPI-1 Binding for FORTRAN and C Collective communication Communication domains and Process groups Point-to-point communication Virtual process

Explain the type of micro-operations, Q. Explain the type of micro-operatio...

Q. Explain the type of micro-operations? Let's first discuss type of micro-operations. Most common micro-operations performed in a digital computer can be categorized into 4 ca

How the information should be retrieved from the database, In a report with...

In a report with an LDB attribute, you do not have to explain how the information should be retrieved from the database tables, but only how the data should be shown on the screen.

In what way the protection fault handler concludes, In what way the protect...

In what way the protection fault handler concludes? After finishing the implementation of the fault handler, it sets the change and protection bits and clears the copy on write

Define dma, Define DMA. The transfer of data among a fast storage devic...

Define DMA. The transfer of data among a fast storage device such as magnetic disk and memory if often limited by the speed of the CPU. Removing the CPU from the path and letti

What is orientation- object-oriented technology, What is Orientation-  obj...

What is Orientation-  object-oriented technology There are many characteristics of object-oriented technology. A few of these characteristics have been discussed in cour

Scanf function, How can the maximum field width for a data item be specifie...

How can the maximum field width for a data item be specified within a scanf function? When the program is executed, three integer quantities will be entered from the standard i

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