Explain the idea of binary search algorithm for arrays. Explain why linked lists

Question

Explain the idea of binary search algorithm for arrays. Explain why linked lists are not suitable data structures for implementing binary search. Consider the following items stored in an integer array: 2, 5, 21, 16, 11, 12, 8, 18, 6. Search for a key value of 16 in the above given array using linear and binary search methods, respectively. Underline the item that is being compared with the key value in each step. Arrange the string "great" in alphabetical order using selection sort. Show each step involved. Consider the incomplete C program given in Figure Q4 that is to automate the above sorting task. Based on the comments provided, complete the program.

Explanation / Answer

Question 4.
a. i. Explain the idea of binary search algorithm for arrays.
The concept of binary search is dividing the array into 2 halves.
Given the leftmost index (low), and rightmost index (high) of the array, mid is
calculated using the formula,
mid = (low + high) / 2.
The 3 possibilities are:
The search key equals the array[mid], i.e., the element is found, therefore,
the search halts.
The search key is less than array[mid], i.e., the element should either be in the
left half or is not found. In this case, adjust high to mid - 1, and run the algorithm again.
The search key is greater than array[mid], i.e., the element should either be in the
right half or is not found. In this case, adjust low to mid + 1, and run the algorithm again.
If low > high, i.e., all the elements in the array are exhausted. Then conclude the element
does not exist.
Note that Binary search algorithm can be applied only on sorted array.
a. ii. Explain why linked lists are not suitable data structures for implementing binary search.
The above algorithm shows that the whole concept i.e., the division of array and moving to
either left or right, is based on the index of the array, and there are no indices in the
linked list, and to find the middle element of the linked list, you have to traverse the whole
array to find the length of the array, and the advantage of binary search is no more.
So, linked list is not suitable data structure for binary search.

b. Consider the array: 2, 5, 21, 16, 11, 12, 8, 18, 6.
The array indices are: 0, 1, 2, 3, 4, 5, 6, 7, 8.
So, going with linear search, starting with index 0, the array will search till the end of
the array. So, the logic is: for(i = 0; i < length of array; i++)   continue comparing the
element in the array with search key, till the search key is found, or till the array exhausts.
array[0] is 2 and is not 16, move forward.
array[1] is 5 and is not 16, move forward.
array[2] is 21 and is not 16, move forward.
array[3] is 16 and is equal to 16, so stop the search.

To apply binary search logic on the same array, first the array should be sorted.
So, the array is: 2, 5, 6, 8, 11, 12, 16, 18, 21.
low = 0, high = 8.
mid = (0 + 8) / 2 = 4.
array[4] is 11. search key 16 is greater than 11, so update low = mid+1 = 5.
low = 5, high = 8.
mid = (5 + 8) / 2 = 6.
array[6] is 16. search key 16 is equal to 16, so stop the search.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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