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

Nmknl''knl, Ask question bhjjnjnnjnjm#Minimum 100 words accepted#

Ask question bhjjnjnnjnjm#Minimum 100 words accepted#

Explain pointers, Explain pointers We can have a pointer pointing to a ...

Explain pointers We can have a pointer pointing to a structure just the same way a pointer pointing to an int, such pointers are called as structure pointers

How to update bios chip, There are two methods to update your BIOS chip: ...

There are two methods to update your BIOS chip: 1. Flash it (software method) 2. Program it with an EEPROM programmer. This is a hardware method. This is how we at BIOSMAN pr

Explain routing tone in strowger telephony, Explain routing tone in strowge...

Explain routing tone in strowger telephony with waveforms and the timings. The call-in-progress tone or routing tone is a 400 Hz or 800 Hz intermittent pattern. In electromec

Describe about the protection features present in ms access, If a programme...

If a programmer doesn't wish to make modifies to the document he can lock the document data and its code from more changes by changing the extension of the file system to .MDE. Cha

Fibre optics, #questifind core radius for single mode operation at 850nm in...

#questifind core radius for single mode operation at 850nm in SI fibre with n1=1.480 & n2=1.47 what is NAon..

Define busy waiting and spinlock, Define busy waiting and spinlock.  Wh...

Define busy waiting and spinlock.  When a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the entry cod

Discuss the concept of segmentation, Discuss the concept of segmentation? ...

Discuss the concept of segmentation? Segmentation is method for the non contiguous storage allocation. This is different from paging as this supports user's view of his program

Processes of information system, Processes of Information System The b...

Processes of Information System The basic purpose of the Information System is to convert and manage data into something that is meaningful. Bocij et al (2003) lists the basic

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