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

How and what data is collected - weather simulation, How and what data is c...

How and what data is collected - Weather simulation -  Sensors measure pressure, relative humidity, temperature and wind speed and wind direction -  Sensors are placed in w

What is functions indention, Use tabs to bring some structure into your fun...

Use tabs to bring some structure into your function body if(nPos > 1) then nRetrun = True else nRetrun = False end if

What is verilog, What is Verilog Verilog  language  is  still  rooted  ...

What is Verilog Verilog  language  is  still  rooted  in  it's  native  interpretative  mode.  Compilation  is  a means of speeding up simulation however has not changed the or

Operating system, explain network operating system and design issues?

explain network operating system and design issues?

Differences between internal and external fragmentation, Explain the differ...

Explain the differences between Internal and external fragmentation. Internal and external fragmentation (1) While memory allocated to a process is a little larger than th

.image forgery detection, what is the code to detect image forgery using Ma...

what is the code to detect image forgery using Matlab..??

What is scan, What is "Scan"? Scan Insertion and ATPG helps test ASICs ...

What is "Scan"? Scan Insertion and ATPG helps test ASICs (e.g. chips) during manufacture. If you know what JTAG boundary scan is, then Scan is the similar idea except that it i

What are the end-to-end layers of osi structure, What are the end-to-end la...

What are the end-to-end layers of OSI structure? The layers 4 to 7 of ISO-OSI reference model communicate along with peer entities into the end systems. Now here is no communi

Where virtual memory is used, Where Virtual memory is used ? Ans. Virtu...

Where Virtual memory is used ? Ans. Virtual memory is utilized in all main commercial operating systems.

What are the major functions of io system, What are the major functions of ...

What are the major functions of IO system?  i. Interface to the CPU and memory by the system bus.  ii. Interface to one or more IO devices by tailored data link.

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