binary search

An array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1=i=n$ such that $A[1 . . i]$ is sorted in the non-decreasing order and $A[i+1 . . n]$...

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

Match the algorithms with their time complexities: Algorithm (P) Towers of Hanoi with n disks (Q) Binary search given n sorted numbers (R) Heap sort given n numbers at the worst ca...

Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. 1. f(int Y[10], int x) { 2. int i, j, k; 3. i =...

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous. 1. f(int Y[10], int x) { 2. int i, j, k; 3. i =...

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the...

The cube root of a natural number n is defined as the largest natural number m such that $${m^3} \le n$$. The complexity of computing the cube root of n (n is represented in binary...

The usual $$\Theta ({n^2})$$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorte...

Which of the following statements is true? I. As the number of entries in a hash table increases, the number of collisions increases. II. Recursive programs are efficient III. The...

Linked lists are not suitable data structures of which one of the following problems?

The recurrence relation that arises in relation with the complexity of binary search is: