The golden ratio search is a divide-and-conquer technique for searching a key in

Question

The golden ratio search is a divide-and-conquer technique for searching a key in a sorted array a. It works similar to the famous binary search but it narrows down possible locations with the aid of the golden ratio, i.e. instead of comparing with the middle element, Golden ratio search examines the element at index = 0.618*n, where n is the number of elements in the sorted array. For example, if you have an array that has 1000 elements, the algorithm will compare the key with the 618 th element instead of the 500 th element as you would do if you use binary search. If the key is less than a[index], the search continues with the first part of the array using the same strategy, if the key is bigger than aindex], the search continues with the second part of the array using same strategy, if the key- a[index], it stops and return the index. The process also stops when the array is empty, indicating the key is not in the array a) Let T(n) be the worse-case time complexity of Golden ratio search. Give a recurrence for the worst-case running time b) Solve the recurrence c) Comparing with the regular binary search, give one possible advantage of binary search and one possible advantage of this algorithm?

Explanation / Answer

public class GoldenRatioSearch {

public static void main(String[] args) {

int[] arr={1,4,2,5,6,9,23,56,12,54,97,77};

int r1=goldenRatioBinarySearch(arr, 9);

int r2=goldenRatioBinarySearch(arr, 55);

System.out.println("r1 "+r1);

System.out.println("r2 "+r2);

}

public static int goldenRatioBinarySearch(int[] arr, int x){

int f=0;

int l=arr.length-1;

while(f<=l){

int m=(f+l)/2;

m=m*golden(arr.length);

if(x==arr[m]){

return m;

}

else if(x>arr[m]){

f=m+1;

}

else{

l=m-1;

}

}

return -1;

}

public static int golden(int n) {

if (n == 0) return 1;

return 1 + 1 / golden(n-1);

}

}

/*

r1 5

r2 -1

*/

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.