Consider a basic, linear search. In a linear search of a sorted data set, you ju

Question

Consider a basic, linear search. In a linear search of a sorted data set, you just examine each element, from the beginning of the list, one at a time, until you either find your value or realize it isn't there -you run out of data, or you go past the spot where the value could have been. 2. Give an example sorted list of at least length 8, and a search value, where the number of comparisons would be the minimum possible number of comparisons. a. b. Use your example and a new search value to show where the number of comparisons is the worst case for the lineasearch(i.e. you have to look at every element in the list)

Explanation / Answer

Hi, this has multiple questions which is not allowed as per chegg policy, please post other one as a separate question, and we will be happy to assist you :)
A) Linear Search, as the questions says, searches a list element by element until we reach the end of the list.

The number of comparisons will be minimums when the element we are searching for is the first element of the list, we check is 1st element is the required element and return, hence only one comparison,
example: in the given list 3 7 8 12 14 22 26 30 32 39
if we search for 3, we only have to do one comparison.
B)Worst case occurs in linear search when the search element is the last element(or for an element thats not present).
in the above example,
if we are searching for 39, we have to iterate through the whole list, hence max number of comparisons.
C)Binary search works on a sorted list, by eliminating half the elements of list, just by one comparison,
   It works like this
Compare with middle element, if matched return
If > middle element, then it can only be in the right part of array, thereby eliminating the need to search left array
if <middle element, then it can only be in the left part of array, thereby eliminating the need to search right array
a. given list is l= 3 7 8 12 14 22 26 30 32 39, and searching for 26
initially,
1.start=0 , end=9(size-1), mid=start+end/2= 4, we compare 26 with l[4] i.e 14, since greater, start=mid+1=5, end=9
2.start=5 , end=9, mid=start+end/2= 7, we compare 26 with l[7] i.e 30, since lesser, end=mid-1=6,start=5
3.start=5 , end=6, mid=start+end/2= 5, we compare 26 with l[5] i.e 22, since greater, start=mid+1=6, end=6
4.start=6 , end=6, mid=start+end/2= 6, we compare 26 with l[6] since equal, we return
Please note we break if start<=end, is not true
b.If we are searching for 6,
comparison 1, 6 with l[mid] i.e 6<14.start=0,end=9,mid=4
    comparison 2, 6 with l[mid] i.e 6<7.start=0,end=3,mid=1
    comparison 3, 6 with l[mid] i.e 6>3.start=0,end=0,mid=0, here start becomes mid+1 i,e 1 and end is 0, since start>end, we break

Thumbs up if this was helpful, otherwise let me know in comments

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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