Here\'s the statement: Binary search does not really correspond to the way human
ID: 3616636 • Letter: H
Question
Here's the statement: Binary search does not really correspond to the way humanssearch through sorted data (such as phone books); instead oflooking in the middle of the list, we estimate the location theitem we are looking for, and search there, and then repeat. Onecould imagine using this method to search a sorted array, byexamining the beginning and ending of the list, and estimating howfar through the list your item is (i.e., if the list begins with 1and ends with 100, you might guess that the number 25 occurs abouta quarter of the way through the list, not in the middle). Write amodified version of Program 2.2, called dictionarySearch, thatimplements this idea on sorted arrays of integers. Then answer thefollowing question: How would you characterize lists for which thismethod will 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 humanssearch through sorted data (such as phone books); instead oflooking in the middle of the list, we estimate the location theitem we are looking for, and search there, and then repeat. Onecould imagine using this method to search a sorted array, byexamining the beginning and ending of the list, and estimating howfar through the list your item is (i.e., if the list begins with 1and ends with 100, you might guess that the number 25 occurs abouta quarter of the way through the list, not in the middle). Write amodified version of Program 2.2, called dictionarySearch, thatimplements this idea on sorted arrays of integers. Then answer thefollowing question: How would you characterize lists for which thismethod will 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; }