Searching

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]$ is sorted in the non-increasing order....

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

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sored in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do { k = (i+j)/2; if (x <= l...

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 = 0; j = 9; 4. do { 5. k = (i + j) /2; 6....

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 = 0; j = 9; 4. do { 5. k = (i + j) /2; 6....

The average number of key comparisons done on a successful sequential search in list of length n is

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