知识卡片
分割点以二分确定枢轴插入处
分割点把较短数组划为不大于枢轴和不小于枢轴的两段;二分搜索能在对数时间内确定该位置。
它只确定边界,并不真的把枢轴插入输入数组。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第26章 并行算法 · 查看原书依据
The procedure returns a split point of A[p : r]: an index q in the range p ≤ q ≤ r + 1 such that all the elements in A[p : q − 1] (if any) are at most x and all the elements in A[q : r] (if any) are at least x. The FIND-SPLIT-POINT procedure uses binary search to find the split point. Lines 1 and 2 establish the range of indices for the search. Each time through the while loop, line 5 compares the middle element of the range with the search key x, and lines 6 and 7 narrow the search range to either the lower half or the upper half of the subarray, depending on the result of the test. In the end, after the range has been narrowed to a single index, line 8 returns that index as the split point.