D1 1.2 - Searching and bin packing
Use binary search to locate an item in an ordered list, then allocate whole items to bins using three packing methods. You will distinguish a valid allocation from a proven minimum, using capacity and item sizes to justify your conclusion.
Binary search on an ordered list
If a number is smaller than the middle value of an ascending list, why inspect anything to the right? Order lets one comparison rule out a whole section.
Binary search
Binary search compares a target with the middle item of an ordered list. If they are equal, the target has been found. Otherwise discard the pivot and the side which cannot contain the target, then repeat on the remaining sublist. An empty sublist means the target is absent.
Use the right-hand middle item when the current sublist has an even number of items. For an ascending list, a smaller target leaves only items before the pivot; a larger target leaves only items after it. In a descending list the inequalities reverse. The original list must be sorted first: a comparison says nothing about the positions of other values in an unordered list.
Keep original positions if the question asks where an item occurs. The middle position within a reduced sublist is not necessarily its original position.
Worked example 1: finding the target
Use binary search to locate in .
Plan. At each stage identify the middle item and explicitly remove it with the rejected side.
| Current sublist | Pivot | Decision |
|---|---|---|
| , position | : discard | |
| , local position | : discard | |
| Equal: found |
Answer. occurs at original position .
Check. Reading the original list confirms that its fourth entry is . Each rejected value is on the wrong side of the target.
Change only the target to . Reaching a one-item list now requires a final comparison rather than an immediate “found”.
Worked example 2: proving absence
Use binary search for in the same ordered list.
Plan. Continue until either equality or an empty sublist occurs.
Answer. The remaining list is empty, so is absent.
Check. The original list jumps from to . The final comparison rules out the only item that remained.
Each unsuccessful comparison must reduce the list.
Watch out
Discard the pivot when it is not the target. Keeping it can repeat a comparison or prevent termination. Do not stop at a singleton without comparing it with the target.
Show the retained sublist or the discarded items at each stage of this search.
First-fit and first-fit decreasing
Packing algorithms allocate indivisible items to containers of a fixed capacity, without exceeding that capacity.
First-fit packing
For first-fit, take items in the given order. Try bin 1, then bin 2, and so on; put the item into the first existing bin with enough space. Open a new bin only if none of the existing bins can take it.
Bins retain their opening numbers. “First” means earliest suitable bin, not most recently opened and not the bin which would leave the smallest space. Exact fits are allowed. Check that every individual item fits in an empty bin before using this model.
For first-fit decreasing, first sort the items into descending order, then apply the identical first-fit rule. The changed order often makes better use of capacity, but does not guarantee the fewest possible bins.
Worked example 3: preserving the given order
Use first-fit to pack into bins of capacity .
Plan. Process the four items in order and test bins from bin 1 every time.
| Item | Placement | Reason |
|---|---|---|
| First | Bin 1 | Open the first bin |
| Second | Bin 1 | |
| First | Bin 2 | Bin 1 has only space |
| Second | Bin 3 | Bins 1 and 2 have and space |
Answer. Bin 1: ; bin 2: ; bin 3: . Three bins are used.
Check. Loads all fit, and their sum equals the total item size. There is spare capacity, but no individual fits into either earlier bin at its turn.
Change only the preprocessing: sort decreasing before packing the same items into the same bins.
Worked example 4: sorting before first-fit
Use first-fit decreasing for , with capacity .
Plan. Write the descending list, then return to bin 1 for every placement.
The first opens bin 1; the next opens bin 2. The first fits bin 1 exactly. The last cannot fit that now-full bin, so goes into bin 2.
Answer. Bin 1: ; bin 2: . Two bins are used.
Check. Both loads are , so all units are allocated without wasted space. Sorting changed the allocation rule's input, not the capacity.
The contrast is useful: a valid first-fit result can use more bins than necessary.
Watch out
Do not rearrange items while carrying out first-fit. For first-fit decreasing, rearrange once at the start; afterwards follow the first available bin rule exactly.
This check uses a different capacity and new item sizes.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account