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 are the advantages and disadvantages of a smart card, What are the adv...

What are the advantages and disadvantages of a Smart Card?    Advantages of Smart Card: 1. It gives convenience & support for multiple currencies over borders. 2. Used

Bangla numeral recognition using multilayer feed forward, Assignment 4: Han...

Assignment 4: Handwritten Bangla Numeral Recognition using Multilayer Feed Forward Neural Network. In this assignment, you will design a multi layer feed forward neural network

What is event-based simulator, Event-based Simulator Digital  Logic  S...

Event-based Simulator Digital  Logic  Simulation  method  sacrifices  performance  for  rich  functionality:  each active signal  is  calculated  for  every  device  it  propa

Find resolution & volts of a 2-digit BCD D/A converter, A 2-digit BCD D/A c...

A 2-digit BCD D/A converter is a weighted resistor type with E R = 1 Volt, with R = 1M? , R f = 10K? . Find resolution in Percent and Volts. Ans. Resolution = 1/2 2 = 0.25 vo

What is the basic approach of page replacement, What is the basic approach ...

What is the basic approach of page replacement?  If no frame is free is available, find one that is not currently being used and free it. A frame can be freed by writing its co

Low level language program, The commands (instructions) are native instruct...

The commands (instructions) are native instructions to the 68HC11 and therefore it is termed a low level language program. Examining the program the instructions (mnemonics) they a

What is the dissimilarity between dynamic strain aging, Q. What is the diss...

Q. What is the dissimilarity between dynamic strain aging and strain aging? Answer:- Strain aging could be explains as "normal wear and tear" or the fatigue that is experi

Describe the three mapping techniques, Describe the three mapping technique...

Describe the three mapping techniques used in cache memories with suitable Example. The cache memory is a fast memory that is inserted among the larger slower main memory and t

DoDAF OV-2 for a green datacenter, How do I create a DoDAF OV-2 for the con...

How do I create a DoDAF OV-2 for the construction of a green data center?

Write a program that will solve a puzzle, You will write a program that wil...

You will write a program that will solve a version of the common newspaper puzzle \word search." In the puzzle you are given a grid lled with characters and a list of words to nd

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