What happens if binary search is used on an unsorted list?

Question

BlackTom AI · Accepted Answer

Binary search requires a sorted array: it compares the middle element to the target and discards the half that cannot contain the target. This prerequisite (sorted order) is the key knowledge point. 1) Relevant concepts - Binary search correctness depends on monotonic order (e.g., nondecreasing). - At each step you compare target t with A[mid]: if t < A[mid] you search left subarray; if t > A[mid] you search right. That reasoning only holds when all left elements are ≤ A[mid] and all right elements are ≥ A[mid]. 2) Step-by-step reasoning with an example Consider A = [10, 3, 8, 1, 6] (unsorted) and target t = 6. Indices 0..4. - Step 1: low = 0, high = 4, mid = (0+4)//2 = 2 → A[2] = 8. - Compare: t (6) < A[2] (8), so binary search chooses left half: new high = mid−1 = 1. - Step 2: low = 0, high = 1, mid = (0+1)//2 = 0 → A[0] = 10. - Compare: t (6) < A[0] (10), so choose left half: new high = −1. - Now low > high → search stops, element reported not found. But A[4] = 6 exists, so the algorithm missed an existing element. 3) Intermediate steps shown above (index calculations, comparisons, updated bounds) demonstrate how choices become invalid when order is not guaranteed. 4) Why the correct answer is correct Because binary search's half-elimination logic assumes sorted order. On an unsorted list those assumptions fail, so the algorithm can incorrectly discard the segment containing the target and thus return wrong results (e.g., fail to find an existing element). 5) Why the other options are incorrect - "It will always find the target": false — as the example shows, it can miss existing elements. - "It will find the target but slower": incorrect — speed is irrelevant if the result is wrong; it may not find the target at all. - "It will sort the list first": standard binary search does not sort the list; sorting would be a separate step and is not part of basic binary search. 6) Conclusion Therefore, using binary search on an unsorted list may give incorrect results, which matches the provided answer.

What happens if binary search is used on an unsorted list?单项选择题

类似问题

Binary Search Considering the following list. {12, 13, 15, 20, 23, 24, 25, 36, 40} What are the two first elements of the list that will be checked to find 25 using binary search? 1: The 1st element 2: The 2nd element

Given the following list of sorted elements, how many elements of the list will be checked to find 25 using binary search? {12, 13, 15, 20, 23, 24, 25, 36, 40}

What is the runtime complexity of the following code? NumberSearch(numbers, N, key) { mid = 0; low = 0; high = N - 1; while (high >= low) { mid = (high + low) / 2; if (numbers[mid] < key) low = mid + 1; else if (numbers[mid] > key) high = mid – 1; else return mid; } return -1; }

What is the prerequisite for using binary search on a list?

Binary search can be implemented using which programming approaches?

In a binary search algorithm, if the middle element is greater than the target, what happens next?

Given a list of 64 elements, how many elements will be checked to look for a value that is larger than the largest value in the list using binary search?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单