Binary search for K=12 in the array A={2, 3, 5, 7,11,15, 16,18,19}

Solutions

Expert Solution

def binarySearch (arr, l, r, x):
   if r >= l:
       mid = l + (r - l) // 2
       # If element is present at the middle itself
       if arr[mid] == x:
           return mid
       # If element is smaller than mid, then it can only be present in left subarray
       elif arr[mid] > x:
           return binarySearch(arr, l, mid-1, x)
       # Else the element can only be present in right subarray
       else:
           return binarySearch(arr, mid + 1, r, x)
   else:
       # Element is not present in the array
       return -1

A = [ 2, 3, 5, 7,11,15, 16,18,19 ]
K = 12

# Function call
result = binarySearch(A, 0, len(A)-1, K)

if result != -1:
print ("Element is present at index {}".format(result))
else:
print ("Element is not present in array")

explanation: Worstcase = O(log n)

beg = 0 and end = 8

mid = 4 so A[4] = 11 is less than K = 12

so the loop moves from 4 to 8

beg =4+1 =5 and end=8

mid = 6 and A[6] = 16 is greater than K=12

so beg = 5 and end changes to 6-1 = 5 and mid = 5

and A[5] =15 is not equal to 12 so element is not there in the array

venereology answered 1 year ago

Next > < Previous

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 −...

// This program demonstrates a Binary Search, which search for a value // in an array,...

// This program demonstrates a Binary Search, which search for a value // in an array, assuming that the array is sorted in descending order. // You have to modify the function binarySearch() to search for a value // in an array that is sorted in ascending order. // NOTES: // Uncomment line 34 and comment line 32. You don't have to edit anything // else in the main(), just in the binarySearch() function. // EXAMPLES (using the array sorted...

Binary Search. Write a MIPS assembly program to perform a binary search on A[10], which is an array of 10 positive integers.

Binary Search. Write a MIPS assembly program to perform a binary search on A[10], which is an array of 10 positive integers. Your program should have a main routine that does the following:(a) Prompt the user to enter all the 10 integers in the array.(b) Prompt the user to enter the number to be searched.(c) Reads the integer values and makes sure it is a positive integer.(d) Prints the index of the integer. If the input is not available in...

Implement a recursive binary search on an array of 8-byte integers in LEGV8

Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the...

Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the template provided under the PolyLearn assignment, using the class TreeNode that is also provided. You may (should) implement helper methods that make your code easier to write, read, and understand. You will also need to write test cases of your own as you develop the methods. You may use iterative and/or recursive functions in your implementation. The following starter files are available . •...

Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum...

Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum element. You need to show the initial and the iteration-level values of the left index, right index and middle index as well as your decisions to reduce the search space in each iteration. 42 39 2 6 9 16 20 28 31 34

Given an array storing integers ordered by value, modify the binary search routine to return the...

Given an array storing integers ordered by value, modify the binary search routine to return the position of the integer with the greatest value less than K when K itself does not appear in the array. Return ERROR if the least value in the array is greater than K.

Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree...

Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree worst case and best case time. Learning Outcomes Describe AVL tree structure Trace and implement AVL tree operations Explain and prove AVL tree performance

Q2 - 15 pts) Given a minimum unimodal array of integers, run the binary search algorithm...

Q2 - 15 pts) Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum element. You need to show the initial and the iteration-level values of the left index, right index and middle index as well as your decisions to reduce the search space in each iteration. 0 1 2 3 4 5 6 7 8 9 33 32 27 26 24 22 21 8 7 3 IN C++ PLEASE

Question 2: Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary...

Question 2: Create a method (sortTraversal) for a Binary Search Tree that prints out the Binary Search Tree in ascending or deceasing order. The order type is an input to the method and can be "ascending" or "descending". The ascending input would return the node values of the tree beginning with the smallest and ending with the largest, descending returns the opposite. Discuss method's Big-O notation. Add proper and consistent documentation to identify code sections or lines to clearly identify...

Subjects