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

Rpn procedure, Apply this algorithm to your MASM program 1) Declare the ...

Apply this algorithm to your MASM program 1) Declare the following variables in your data segment: .data ; ; These are the values of the variables ; Variables

C, "Super ASCII", if it contains the character frequency equal to their asc...

"Super ASCII", if it contains the character frequency equal to their ascii values. String will contain only lower case alphabets (''a''-''z'') and the ascii values will starts from

Determine about the security policy, Determine about the Security Policy ...

Determine about the Security Policy In the United States, the government has a separate organisation looking after the security measures and providing guidelines to all departm

Automatic typewriter in information distribution, Automatic typewriter : I...

Automatic typewriter : It is a power-driven machine, which automatically types a standard pro forma from a previously punched or stencilled master. When the master is placed on th

Write a program to event advertised, A museum has a collection of old poste...

A museum has a collection of old posters advertising events of various kinds (theatre, sport, fairs, lectures etc.). It wishes to keep a record of these, containing, for each poste

What is drawbacks of cd- rom, Q. What is Drawbacks of CD- ROM? Drawbac...

Q. What is Drawbacks of CD- ROM? Drawbacks of CD- ROM are as below: 1. It is read-only and can't be updated. 2. It has an access time much longer than magnetic disk dri

How are comparisons done in 8086 assembly language, Q. How are comparisons ...

Q. How are comparisons done in 8086 assembly language? There is a compare instruction CMP. Though this instruction just sets the flags on comparing two operands (both 16 bits

Poor technology or system requirements definition, Poor Technology or Syste...

Poor Technology or System Requirements Definition - Information System Previously we looked at product design and specifically the importance of requirements capture as part o

Paging supervisor - computer architecture, Paging supervisor: This par...

Paging supervisor: This part of the operating system built and manages the page tables. If the  due to dynamic address translation hardware a page fault occurs exception then

Strategy used for the project design, This project is divided to two parts ...

This project is divided to two parts (hardware and software) each with is subtask and consideration was given in all areas in order to meet the target specification. Solutions are

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