Question

State True or False. i) Binary search is used for searching in a sorted array. AND...

State True or False. i) Binary search is used for searching in a sorted array. AND ii) The time complexity of binary search is O(log n). A) True, False B) False, True C) False, False D) True, True Explain

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

D) TRUE,TRUE.

i) Binary search searcha sorted array by repeatedly dividing the search interval in half .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.Otherwise, narrow it to th eupper half.Repeat the steps and check untill the value is found or the interval becomes empty.

ii) The time Complexity of Binary search is O(log n)

.

-------------------------------------------------thank You----------------------------------------------------------------------------------

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Select All true answers about linear and binary search 1. The advantage of linear search is...
Select All true answers about linear and binary search 1. The advantage of linear search is that it runs in O(1) space complexity and binary search can only run in O(logn) space complexity 2. The disadvantage of binary search is that it requires the container to be sorted which linear search does not. 3. The advantage of binary search over linear search is that is more efficient O(logn)versus O(n) average/worst case). 4. The advantage of linear search is that it...
Assume that we have a sorted array a[n]with n non-negative numbers. a. Develop an algorithm using...
Assume that we have a sorted array a[n]with n non-negative numbers. a. Develop an algorithm using divide-and-conquer to search for an element x in this sorted array a[n]. This algorithm will take an input of a sorted array a[n], and return the index of element x is an element of a[n], or return -1if xis NOT an element of this array. b. Analyze the time complexity of this algorithm.
how to pass in an object from an array of objects in a binary search on...
how to pass in an object from an array of objects in a binary search on swift? I have the following:    func binarySearchPrefix(array: [String], target: String) -> Bool {                var left = 0         var right = array.count - 1                while (left <= right) {             let mid = (left + right) / 2             let value = array[mid]             if (value.hasPrefix(target)) {                 return true             }             if (value < target) {                ...
Match the following. a) Completeness i) How long does it take to find a solution b)Time...
Match the following. a) Completeness i) How long does it take to find a solution b)Time Complexity ii) How much memory need to perform the search. c) Space Complexity iii) Is the strategy guaranteed to find the solution when there in one. Explain A) a-iii, b-ii, c-i B) a-i, b-ii, c-iii C) a-iii, b-i, c-ii D) a-i, b-iii, c-ii The number of comparisons done by sequential search of N elements in an array is ……………… A) (N/2)+1 B) (N+1)/2 C)...
Complete the following function (detailed instructions are given below the code): private static int predecessor(int array[],...
Complete the following function (detailed instructions are given below the code): private static int predecessor(int array[], int arrayLen, int key) { // Complete this function. } Given a set of numbers, the predecessor of a number x is the highest number in the set that is less than or equal to x. Thus, if I have the set {6; 9; 10; 13; 22; 31; 34; 88}, then the predecessor of 31 is 31 itself, whereas the predecessor of 30 is...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
IN JAVA Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort: <-- (I need the...
IN JAVA Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort: <-- (I need the code to be written with these) I need Class river, Class CTRiver and Class Driver with comments so I can learn and better understand the code I also need a UML Diagram HELP Please! 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()...
Using Big O notation, indicate the time requirement of each of the following tasks in the...
Using Big O notation, indicate the time requirement of each of the following tasks in the worst case. Computing the sum of the first n even integers by using a for loop            [ Choose ] O(1) O(2n) O(n*log n ) O(2^n) O(log n) O(n^2) O(n) O(2) O(n^3)          Displaying all n integers in an array            [ Choose ] O(1) O(2n) O(n*log n ) O(2^n) O(log n) O(n^2) O(n) O(2) O(n^3)          Displaying all n integers in a sorted linked chain            [ Choose...
#data structures Give the appropriate execution time efficiency of the following array algorithms using Big-O notation....
#data structures Give the appropriate execution time efficiency of the following array algorithms using Big-O notation. Assume the size of the array is n. a)   Linear Search (average case)   ______________________    b)   Binary Search (worst case)       ______________________    c)   Insertion Sort (best case)       ______________________    d)   Insertion Sort (average case)           ______________________    e)   Quick Sort (average case)           ______________________
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT