StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Smells like homework because there are generally <em>better</em> methods to implement the design.</p> <p>Let me clarify the requirement: Given an array of contiguous integers, they can be perceived to be in the following order:</p> <pre><code>row 0: array[0] # row 1: array[1] # # row 2: array[3] # # # # row 3: array[7] # # # # # # # # </code></pre> <p>The search algorithm, according to my understanding, is:</p> <p><strong>1. Outer binary search</strong></p> <p>Apply a binary search to the first "column". The result will find the row to search.</p> <p><strong>2. Row binary search</strong></p> <p>Apply a binary search to the row to find the exact value.</p> <h2>The Outer Binary Search</h2> <p>The next step is to modify an existing binary search algorithm to advance the "lowest" and "highest" indices according to the array layout.</p> <p>Looking at the layout above, there appears to be a pattern with the array indices for each row. Looks like:</p> <pre><code> [Equation 1] index = power(2, row #) - 1 </code></pre> <p>In a binary search, each iteration picks a midpoint, which is half way between the highest point and the lowest point, normally calculated as:</p> <pre><code>[Equation 2} midpoint = ((highest - lowest) / 2) + lowest </code></pre> <p>To make the understanding easier, let us adopt two indexing conventions: <em>row index</em> and <em>column index</em>. The <em>row index</em> is the row number, according to the layout. The <em>column index</em> will be the position within the row. The layout above contains 4 rows. Row 2 has 4 columns.</p> <p>So to find the row, we use the midpoint formula:</p> <pre><code> row_midpoint = ((row_highest + row_lowest) / 2) + row_lowest </code></pre> <p>Before a value can be compared it must be located first. The location is obtained by plugging the <em>row_midpoint</em> value into Equation 1.</p> <pre><code>array_midpoint_index = (1 << row_midpoint) - 1 </code></pre> <p>The value is then obtained by using this <em>array_midpoint_index</em>: value = array[array_midpoint_index]</p> <p>To avoid repeating calculations, I recommend saving the values, such as <em>row_low_value</em> and <em>row_high_value</em> as examples.</p> <p>After the exact row is found it is time for the ...</p> <h2>Row Binary Search</h2> <p>The binary search applied to the row is an augmented binary search. The augmentation is determining the array indices of the first and last columns of the row. These column indices can be computed using Equation 1.</p> <p>Details are left as an exercise for the reader.<br> <em>(BTW, making pictures and diagrams is always a helpful practice when getting stuck on a problem, whether it be computer algorithms or physic's word problems.)</em></p> <h2>Maintaining the Data Structure</h2> <p>Maintenance of this data structure, inserting and removing elements, is easiest performed by treating it as a single array. Once the insertion index is found, move elements <em>down</em> to make room for another, then insert the new element.</p> <h2>A Better Data Structure</h2> <p>A <em>better</em> data structure may be to have an array of <code>[value, pointer, length]</code> elements. The pointer would point to another array. The <em>length</em> field indicates the length of the array. This allows for using a standard binary search on the value field. A standard binary search can be applied to the <em>row</em> array by using the <em>pointer</em> and <em>length</em> fields. The convenience is that the C and C++ languages come with standard binary search functions, <em>already tested that you don't have to waste time rewriting</em>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload