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

Techno hype - obstacle to information system, Techno hype - Obstacle to Inf...

Techno hype - Obstacle to Information System New technology has always been accompanied by a certain amount of euphoria that inevitably leads to unrealistic expectations place

Name the two operations of stack, Name the two operations of stack A st...

Name the two operations of stack A stack has only two operations and they are insertion and deletion of items. The operation insertion is called push (or push-down) as it can b

Mips assembly language equivalents , MIPS' native assembly code only has tw...

MIPS' native assembly code only has two branch instructions, beq and bne, and only one comparison instruction, slt. Using just these three instructions (along with the ori instruct

Megaflops, Speed in scientific computing is measured in megaflops, gigaflop...

Speed in scientific computing is measured in megaflops, gigaflops, teraflops and petaflops. A megaflop is 10 6 floating point arithmetic operations (+, -, *, /) in one second What

What is a resource-allocation graph, What is a resource-allocation graph? ...

What is a resource-allocation graph? Deadlocks can be described more precisely in terms of a directed graph known as a system resource allocation graph. This graph having of a

What is a process scheduling, What is a Process Scheduling? Scheduling...

What is a Process Scheduling? Scheduling is a key element of the workload management software that usually performs several or all of: Queuing Scheduling Monito

Term memory as used in a computer context initially, Term memory as used in...

Term memory as used in a computer context initially The term memory as used in a computer context initially referred to magnetic core memory devices which were used beginning

The number of control lines for a 8 – to – 1 multiplexer, What is the numbe...

What is the number of control lines for a 8 - to - 1 multiplexer ? Ans. There are 3 control lines, for an 8 to 1 Multiplexer. The control signals are utilized to steer any one

Computer systems principles, Your program should print the inverted map to ...

Your program should print the inverted map to the screen (using a format similar to the inverter project, but you will print out the url values instead of document IDs). You can pr

Public key infrastructure solutions, Public Key Infrastructure solutions ...

Public Key Infrastructure solutions The use of public-key based security systems requires great attention and due care in design and management of security features. The secur

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