Question

In: Computer Science

Consider the recursive formulation of the Binary Search algorithm. Given a sorted and non-decreasing list of...

Consider the recursive formulation of the Binary Search algorithm. Given a sorted and non-decreasing list of comparable objects L, and a new item x, find the location (index) of x or indicated that x is not in L.

5a) Give a recursive algorithm for binary search. No, while, for, repeat etc statements are allowed. Only if, if else and assignment statements are allowed.

5b) Write a difference equation for the running time of your Binary Search algorithm. Solve your equation and express the performance of the algorithm in Θ(·) notation.

Solutions

Expert Solution

SOLUTION:

BINARY SEARCH :

Search a sorted array by repeatedly dividing the search interval in half.

Begin with an interval covering the whole array.

Consider array to be sorted in non-decreasing order (i.e. ascending order as mentioned in the question)

If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half of the array. Otherwise narrow it to the upper half.

Repeatedly check until the value is found or the interval is empty.

The logic is to keep ignoring a half of the search array after every comparison

Algorithm Explanation (recursion algorithm):

List of array = L

New item to be searched = x

  1. Compare x with the middle element of L.
  2. If x matches with middle element of L, we return the mid index (location/index of x).
  3. Else If x is greater than the mid element of L, then x can only lie in upper-half subarray after the mid element. So, recur for right half.
  4. Else (x is smaller) recur for the lower-half.

Algorithm:

BS (L, lower, upper)

{

            if ( lower < upper)

            {

                        mid = (lower + upper) / 2;

                        if ( x = = L[mid] )

                                    return mid;

                        else if ( x < L[mid] )

                                    return BS (L, lower, mid-1)

                        else

                                    BS (L, mid+1, upper)  

            }

            Print (“x Not Found”);

}

Time Complexity:

The time complexity of Binary Search can be written as (the array is getting divided into half of itself with every check):

T(n) = T(n/2) + c ;where, T(1) = 1

**********************************************************

Please comment for any further help on this question.


Related Solutions

(a) Consider the general k-ary search algorithm (generalization of binary search) which splits a sorted array...
(a) Consider the general k-ary search algorithm (generalization of binary search) which splits a sorted array of size n into k subsets each of size n/k and recursively searches only one of these k subsets. Which one of these k subsets should be searched is decided by making (k − 1) comparisons, each of which can be done in constant time. Clearly, the recurrence relation for this k-ary search algorithm can be written as, T(n) = T(n/k) + (k −...
python3: Given a list of numbers in order order, return a new list sorted in non-decreasing...
python3: Given a list of numbers in order order, return a new list sorted in non-decreasing order, and leave the original list unchanged. function only def mergeSort(inputArray): #code here a = [3,4,6,1,21,11,9,8] b = mergeSort(a) print('original array is: ', a) print('sorted array is: ', b)
Write a recursive method to implement Binary Search of a sorted integer array. Signature of method...
Write a recursive method to implement Binary Search of a sorted integer array. Signature of method could be public int BinarySearch(int target, int low, int high)
Write a recursive method to implement Binary Search of a sorted integer array. Signature of method...
Write a recursive method to implement Binary Search of a sorted integer array. Signature of method could be public int BinarySearch(int target, int low, int high)
Create a List object that uses the binary search algorithm to search for the string "A"....
Create a List object that uses the binary search algorithm to search for the string "A". Display a message box indicating whether the value was found. Language: C#
Write a modification of the recursive binary search algorithm that always returns the smallest index whose...
Write a modification of the recursive binary search algorithm that always returns the smallest index whose element matches the search element. Your algorithm should still guarantee logarithmic runtime. Give a brief discussion of the best- and worst-case runtimes for this new algorithm as they compare to the original. NOTE: You do not have to re-write the entire algorithm. You just need to indicate any changes you would make and show the pseudocode for any portions that are changed. Example: Given...
Binary Search Algorithm a.) Create a Java application that utilizes the "Binary Search Algorithm" presented in...
Binary Search Algorithm a.) Create a Java application that utilizes the "Binary Search Algorithm" presented in chapter 19 (NOT Java's pre-built binarySearch() method from imported Java library) to search for an integer in a random array of size 30 in the range of 0 to 1000 inclusive. You should use Java's random number generator to randomize the numbers in your array. b.) The application's main() method should display unsorted array and sorted array, prompt user for a search key, allow...
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array...
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time. Return that integer. Input: arr = [1,2,2,6,6,6,6,7,10] Output:
Write a recursive algorithm in pseudo-code to compute the “power list” of a given list of...
Write a recursive algorithm in pseudo-code to compute the “power list” of a given list of integers. Assume that the List type has members: int List.length returns the length of the list. void List.push(T n) pushes an element n to the front of the list T List.pop() pops an element from the front of the list. List$$ List$$.concat(List$$ other) returns the concatenation of this list with other. Explain in plain English the reasoning behind your algorithm. Power Lists should be...
Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort I need it in Java with...
Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort I need it in Java with comments and I need the input file to be placed with Scanner not BufferedReader Please help I need Class River Class CTRiver and Class Driver Class River describes river’s name and its length in miles. It provides accessor methods (getters) for both variables, toString() method that returns String representation of the river, and method isLong() that returns true if river is above 30 miles...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT