Purchase Solution

Execution of Binary Search Algorithm

Not what you're looking for?

Ask Custom Question

See the attached file.
Given algorithm looks for a value in a nondecreasing sequence and returns the index of the value if it is found or 0 if it is not found.

Input: A sequence si, ...... ,sj (j >= i >= 1) sorted in nondecreasing order, a value key, i, and j
Output: The output is an index k for which sk = key, or if key is not in the sequence, the output is the value 0.

binary_search(s, i, j, key) {
if (i > j) // not found
return 0
k = (i + j)/2
if (key == sk) // found
return k
if (key < sk) // search left half
j = k - 1
else // search right half
i = k + 1
return binary_search(s, i, j, key)
}

Consider the sequence s1 = 'C', s2 = 'G', s3 = 'J', s4 = 'M', s5 = 'X'. Show how the algorithm executes in case key = 'C'.

Attachments
Purchase this Solution
Solution Summary

Attached document gives statement by statement execution of each binary_search call, explaining the execution/non-execution of individual statements during the call. Additionally it counts the number of operations at algorithm level during each call, excluding the contribution from recursive call.

Purchase this Solution
Free BrainMass Quizzes
Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.

Javscript Basics

Quiz on basics of javascript programming language.

C# variables and classes

This quiz contains questions about C# classes and variables.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

View More Free Quizzes
Related BrainMass Solutions

  • Runtime Analysis of Search Algorithm

    We analyze the runtime of a seqential search and binary search algorithm.

  • converting ternary to binary

    Note that the algorithm returns a binary tree.

  • heap structure

    The primary advantage of the heap sort is its efficiency. The execution time efficiency of the heap sort is O(n log n).

  • Create a Java Program To Compare Two Search Algorithms

    Program generates an array of 30 unique random numbers in the range 0-99, and then sorts them before accepting user input to search for in this array. Source code implements simple linear search and binary search.

  • Binary Search Trees in C++

    A C++ program is written to implement phone book application using template based Binary Search Tree algorithm.

  • Detailed comparision of linear and binary searches on a list

    A dictionary whose words are not sorted is simply a list of unsorted elements and therefore the search time is O(n). Now, if the list is sorted (either ascending or descending) then we can use a binary search algorithm to search the data.

  • NP - Completeness Minimization Problem

    The basic idea of my algorithm is binary search. Suppose A(x,k) is the algorithm that solves the decision version of P with instance x and size k.

  • binary search

    2586 Understanding a Binary Search. What is a binary search, and how does it work? Binary Search is arguably one of the most useful algorithms you will come across.

  • Proving O(log n) comparisons in key compaisons binary search

    50555 Proving O(log n) comparisons in key comparisons binary search Prove that any binary search algorithm on a sorted array of size n that uses only key comparisons must require at least omega (log n) comparisons in the worst case.

View More Related Solutions