Here\'s the statement: Binary search does not really correspond to the way human

Question

Here's the statement: Binary search does not really correspond to the way humans searchthrough sorted data (such as phone books); instead of looking inthe middle of the list, we estimate the location the item we arelooking for, and search there, and then repeat. One could imagineusing this method to search a sorted array, by examining thebeginning and ending of the list, and estimating how far throughthe list your item is (i.e., if the list begins with 1 and endswith 100, you might guess that the number 25 occurs about a quarterof the way through the list, not in the middle). Write a modifiedversion of Program 2.2, called dictionarySearch, that implementsthis idea on sorted arrays of integers. Then answer the followingquestion: How would you characterize lists for which this methodwill perform better than binary search?
(Program 2.2 is in the bottom of this post)
I've been trying really hard to do this assignment and cannotfigure it out, my mind is stuck on binary search!
I'll rate lifesaver to the person who helps first! THANKS!
Program 2.2 Binary search
static int search(int a[], int v, int l, int r) { while (r >= 1)    { int m = (l + r )/2;    if (v == a[m]) return m;    if (v < a[m]) r = m -1; else l = m+1;    } return -1; } Binary search does not really correspond to the way humans searchthrough sorted data (such as phone books); instead of looking inthe middle of the list, we estimate the location the item we arelooking for, and search there, and then repeat. One could imagineusing this method to search a sorted array, by examining thebeginning and ending of the list, and estimating how far throughthe list your item is (i.e., if the list begins with 1 and endswith 100, you might guess that the number 25 occurs about a quarterof the way through the list, not in the middle). Write a modifiedversion of Program 2.2, called dictionarySearch, that implementsthis idea on sorted arrays of integers. Then answer the followingquestion: How would you characterize lists for which this methodwill perform better than binary search?
(Program 2.2 is in the bottom of this post)
I've been trying really hard to do this assignment and cannotfigure it out, my mind is stuck on binary search!
I'll rate lifesaver to the person who helps first! THANKS!
Program 2.2 Binary search
static int search(int a[], int v, int l, int r) { while (r >= 1)    { int m = (l + r )/2;    if (v == a[m]) return m;    if (v < a[m]) r = m -1; else l = m+1;    } return -1; } Program 2.2 Binary search
static int search(int a[], int v, int l, int r) { while (r >= 1)    { int m = (l + r )/2;    if (v == a[m]) return m;    if (v < a[m]) r = m -1; else l = m+1;    } return -1; }

Explanation / Answer

please rate - thanks import java.util.*;    public class untitled       { public static void main( String [] args )         { Scanner in= newScanner(System.in);         int size = 11,num;         int [ ] a = new int[]{2,10,17,45,49,55,68,85,92,98,110};         System.out.println("whatare you looking for? ");                num=in.nextInt();                System.out.println( "Found " + num + " at" +                                 search( a, num,0,size-1 ) );                  } static int search(int a[], int v, int l, int r) {double percent; while (r >= 1)    {       int m = (a[r] - a[l] );        percent=v/(double)m;        m=(int)((r-l)*percent);       if (v == a[m]) return m;       if (v

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---