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

Describe about directory in doc, Q. Describe about directory in DOC? We...

Q. Describe about directory in DOC? We all know that, the volume of the hard disk is generally quite large (10 MB to a few GB). You can keep hundreds or even thousands of files

Give the difference b/w multiprogramming and multiprocessing, Give the diff...

Give the difference between multiprogramming and multiprocessing. A multiprocessing system is a computer hardware configuration which contains more than one independent proc

Explain the storage class extern, Explain The Storage Class extern The...

Explain The Storage Class extern The Storage Class extern : One method of transmitting information across blocks and functions is to use external variables. When a variable is

Classical approach - canonical genetic algorithm, Classical approach - Cano...

Classical approach - Canonical genetic algorithm: However returning to the classical approach, as there example, whether solving a particular problem involved finding a set of

Average number of instructions, Consider a processor with a 4-stage pipelin...

Consider a processor with a 4-stage pipeline. Each  time a conditional branch is encountered, the pipeline must be flushed (3 partially completed instructions are lost). Determine

Dynamic cons, i want dynamic cons simple program in c++

i want dynamic cons simple program in c++

Numbers of students must be integer, A school district has I neighbourhoods...

A school district has I neighbourhoods, J schools and G grades at every school. Every school j has a capacity of C jg for grade g. In every neighbourhood i, the student population

What is frontpage, Front page is a software used to make a webpage.

Front page is a software used to make a webpage.

Define the programmable logic devices (pld), Define the Programmable logic ...

Define the Programmable logic devices (PLD)? In the world of digital electronic systems there are three essential kinds of devices 1.memory, 2.microprocessors, and 3.logic. The

What is file allocation table, Q. What is File allocation table? FAT ma...

Q. What is File allocation table? FAT maps the usage of data space of disk. It comprises information about space used by every individual file and unused disk space as well as

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