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

Write a menu driven program to find 10''s complement, Q. Write a menu dri...

Q. Write a menu driven program to find 9's and 10's complement of a decimal number using file. Perform necessary validation with proper message that entered numbers must be de

What are the components of i-way infrastructure, What are the components of...

What are the components of I-way Infrastructure? There are three components of the I-way infrastructure: • Consumer access equipment • Local on-Ramps • Global informat

Which is the slowest sorting procedure, The slowest sorting procedure is   ...

The slowest sorting procedure is    Bubble Sort is the slowest sorting process.

What do you meant by erp, Question 1: What do you meant by ERP? What ar...

Question 1: What do you meant by ERP? What are the benefits of ERP? Definition of ERP Question 2: Describe briefly the advantages of the ERP. Explanation of six advanta

Describe about the layered computer design, Describe about the Layered comp...

Describe about the Layered computer design Introduction Layered computer design focuses on computer design. It uses top-down, layered approach to design and also to improve

Define locality of reference, Define locality of reference? What are its ty...

Define locality of reference? What are its types?  During the course of implementation of a program memory references by the processor for both the instruction and the data ten

What are the 3 segments of the default route, What are the 3 segments of th...

What are the 3 segments of the default route, that is there in an ASP.NET MVC application? Ans)  Segment 1st - Controller Name Segment 2nd - Action Method Name Segment 3r

COA, During instruction execution, there are other parts of the CPU that ca...

During instruction execution, there are other parts of the CPU that can determine when a physical register might be freed. Briefly describe where else we can put freeing logic and

Show error detection mechanism, Q. Show Error detection mechanism? Erro...

Q. Show Error detection mechanism? Error detection mechanism can be described as below: Figure: Error detection and correction

Explain about distributed shared memory systems, Explain about Distributed ...

Explain about Distributed Shared Memory Systems? Distributed Shared Memory (DSM) systems emulate a shared memory abstraction on loosely coupled architectures in order to allow

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