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

Classify data networks, Classify data networks. Data Network Classifica...

Classify data networks. Data Network Classifications: Data Networks are classified as per to their geographical coverage: - Wide area networks (WANs) - Metropolitan ar

Communication of request/response - procedural interaction, Explain the Com...

Explain the Communications of Request/Response Communications requirements for message or procedural- based interaction are very similar. Application interaction (client-server

What is a multiplexer tree, What is a Multiplexer Tree? Ans Multip...

What is a Multiplexer Tree? Ans Multiplexer Tree: The largest available MUX IC is 16 to 1. Meeting the larger input requires there must be a provision to expand this. It

Mac and llc, how can we improve the way LLC and MAC are used for LAN operat...

how can we improve the way LLC and MAC are used for LAN operation.?

What is view, What is View? A simple view can be thought of as a subset...

What is View? A simple view can be thought of as a subset of a table. It can be used for retrieving data, as well as updating or deleting rows. Rows updated or deleted in the v

Implementing recursive function the data structure, For executing recursive...

For executing recursive function the data structure used is: For executing recursive function, stack is used as a data structure.

Explain about memory buffer register, Q. Explain about Memory Buffer Regist...

Q. Explain about Memory Buffer Register? Memory Buffer Register (MBR): It's a register that comprises the data to be written in memory (write operation) or it obtains the data

Multi-threaded processors, Multi-Threaded Processors In unit 2, we have...

Multi-Threaded Processors In unit 2, we have gone through the use of distributed shared memory in parallel computer architecture. Although the use of distributed shared memory

How branching takes place in instruction pipeline, How branching takes plac...

How branching takes place in Instruction pipeline. Explain with suitable examples

Database management system, what would be the occupancy of each leaf node o...

what would be the occupancy of each leaf node of a B+ tree

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