知识卡片

普通读书笔记卡 · 3673.a.1

分割点以二分确定枢轴插入处

理解等级:中级

分割点把较短数组划为不大于枢轴和不小于枢轴的两段;二分搜索能在对数时间内确定该位置。

它只确定边界,并不真的把枢轴插入输入数组。

这张卡片看不懂?

已有反馈 · 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.

    参考来源

    - 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[70000,75000))。 - 结论依据:第26章 FIND-SPLIT-POINT 第1–8行:在有序数组上用二分返回 q,使左侧元素≤x、右侧元素≥x;前文指出这相当于 x 的假想插入位置,算法不改写输入数组。 - 原始内容: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 F IND -S PLIT -P OINT 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. - 旁证(文本字符[65000,70000)):Intuitively, the subarray A [ p 2 : r 2 ] would still be sorted if x were inserted between A [ q 2 −1] and A [ q 2 ] (although the algorithm doesn’t do that).