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 a header represents in CGI document, A Header in CGI document can repr...

A Header in CGI document can represent? A header into CGI document can show format of the document and the location if document used to various URL.

Explain segmentation, Explain segmentation? Segment memory addressing ...

Explain segmentation? Segment memory addressing divides memory into many segments. Each of these segments can be considered as a linear memory space. Every one of these segmen

Single bus structures, Single BUS STRUCTURES : The Bus structure and ...

Single BUS STRUCTURES : The Bus structure and multiple bus structures are kinds of bus or computing. A bus is fundamentally a subsystem which transfers data amongst the compo

what is a persistent cookie in php, A persistent cookie is a cookie which ...

A persistent cookie is a cookie which is keeps in a cookie file permanently on the browser's computer. By default, cookies are formed as temporary cookies which keep only in the br

How many instructions in a computer, Q. How many instructions in a Computer...

Q. How many instructions in a Computer? A computer can have a vast number of instructions and addressing modes. Older computers with the growth of Integrated circuit technolog

Find the complement of following functions, Q. Find the complement of follo...

Q. Find the complement of following functions and reduce to minimum literals 1. (A+C+D) (A+C+D') (A+C'+D)(A+D') 2. ABC(ABC' + AB'C + A'BC) 3. AB + AB' + A'C +A'C'

Digital Design, Design a serial 2’s complementer with a shift register and ...

Design a serial 2’s complementer with a shift register and a flip-flop

The concept of program-parallel computing, The Concept of Process Infor...

The Concept of Process Informally, a method is a program in execution, behind the program has been loaded in the main memory. However, a method is more than just a program code

Functionality of hyper thread processor, Hyper-threading works by duplicati...

Hyper-threading works by duplicating those sections of processor that kept the architectural state-but not duplicates the main implementation resources. This allows a Hyper-threadi

Explain the transport layer in detail, Explain the transport layer in detai...

Explain the transport layer in detail. Transport Layer: The transport layer controls and makes sure the end-to-end integrity of the data message propagated by the network am

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