1. Search: Given the following sorted array of 150 numbers from 0 to 999 3 7 11

Question

1. Search: Given the following sorted array of 150 numbers from 0 to 999 3 7 11 12 18 25 31 36 48 51 57 59 65 73 84 88 94 97 110 119 137 142 151 158 161 174 176 179 185 192 194 208 217 221 228 232 235 241 242 243 251 257 260 262 274 282 285 290 293 304 310 313 317 325 341 346 350 356 365 373 381 382 388 400 417 421 425 429 432 441 450 455 458 461 472 482 488 495 502 507 511 516 523 526 528 539 547 552 556 563 572 573 574 579 592 599 604 610 617 628 637 642 648 655 668 669 674 679 683 692 701 709 717 736 745 751 753 759 772 775 781 786 792 794 803 807 818 821 825 834 841 847 853 858 871 875 884 888 892 902 924 926 938 945 955 961 974 982 989 995 Count how many comparisons are made by (1) linear search guessing at the closer end, (2) binary search, and (3) interpolation search, in searching for (a) 161, (b) 461, and (c) 880. Present your results in the form of a table. You may write a program or programs to do this.

Explanation / Answer

The resultant table is as follows: -

I used below code to get above values: -

SearchComparisons.java

package searchComparison;

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class SearchComparisons {
  
   public static int count = 0;
   public static void main(String[] args) {
       int arr[] = {3,7,11,12,18,25,31,36,48,51,
               57,59,65,73,84,88,94,97,110,119,137,142,151,
               158,161,174,176,179,185,192,194,208,217,221,228,
               232,235,241,242,243,251,257,260,262,274,282,285,290,
               293,304,310,313,317,325,341,346,350,356,365,373,381,382,
               388,400,417,421,425,429,432,441,450,455,458,461,472,482,488,
               495,502,507,511,516,523,526,528,539,547,552,556,563,572,573,574,
               579,592,599,604,610,617,628,637,642,648,655,668,669,674,679,683,692,
               701,709,717,736,745,751,753,759,772,775,781,786,792,794,803,807,818,821,
               825,834,841,847,853,858,871,875,884,888,892,902,924,926,938,945,955,961,974,982,989,995};
      
       int numToSearch=161;
       int numOfCOmparisonsForLinear = LinearSearch(arr,numToSearch);
       int foundBinary = bs(arr,0,arr.length-1,numToSearch);
       int numOfCOmparisonsForBinary = count;
      
       ArrayList<Integer> intList = new ArrayList<Integer>();
       for (int index = 0; index < arr.length; index++)
       {
       intList.add(arr[index]);
       }
       Collections.sort(intList);
       int[] arrs = new int[intList.size()];
       for (int i = 0; i < intList.size(); i++) {
           arrs[i] = intList.get(i);
       }
       interpolationSearch(arrs,numToSearch);
       int numOfCOmparisonsForInterpolation = count;
      
       System.out.println("Linear:"+numOfCOmparisonsForLinear);
       System.out.println("Binary:"+numOfCOmparisonsForBinary);
       System.out.println("interpolation:"+numOfCOmparisonsForInterpolation);
   }
  
   public static int interpolationSearch(int[] sortedArray, int toFind)
{
      
int low = 0;
  
int high = sortedArray.length - 1;
int mid;
while (sortedArray[low] <= toFind && sortedArray[high] >= toFind)
{
if (sortedArray[high] - sortedArray[low] == 0) {
   count++;
   return (low + high)/2;
}
  
mid = low + ((toFind - sortedArray[low]) * (high - low)) / (sortedArray[high] - sortedArray[low]);

if (sortedArray[mid] < toFind) {
low = mid + 1;
count++;
}
else if (sortedArray[mid] > toFind) {
high = mid - 1;
count++;
}
else {
   return mid;
     
}
}
if (sortedArray[low] == toFind) {
   count++;
   return low;
  
}
  
/** not found **/
else
   return -1;
  

   }
  
   //binary search
   public static int bs(int[] items, int start, int end, int goal)
   {
       count += 1;
   if (start > end){
       return (-1);
   }
   else
   {
   int mid = (start + end)/2;
   if (goal == items[mid]) {
           count += 1;
           return (mid);
       }
   else
   if (goal < items[mid])
   return (bs(items, start, mid - 1, goal));
   else
   return (bs(items, mid + 1, end, goal));
   }
   }
  
   public static int LinearSearch(int[] array,int search) {
       int numComparisons =0;
       int c;
       for (c = 0; c < array.length; c++)
   {
           numComparisons++;
   if (array[c] == search) /* Searching element is present */
   {
       break;
   }
   }
   if (c == array.length)numComparisons++; /* Searching element is absent */
  
      
       return numComparisons;
   }
}

Sample Output for searching 161: -

Linear:25
Binary:8
interpolation:9

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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