Modified binary search

[darwinrlo]

If the middle element is greater than the target element,

Example: [1, 2, 5, 7], target = 4

• Iteration 1: [1 (s), 2 (m), 5, 7 (e)]
  • The middle element is less than the target.
• Iteration 2: [1, 2, 5 (s, m), 7 (e)]
• Iteration 3: [1, 2 (e), 5 (s), 7] (terminate)
  • e is placed before s.

Example: [1, 2, 3, 5], target = 4

• Iteration 1: [1 (s), 2 (m), 3, 5 (e)]
  • The middle element is less than the target.
• Iteration 2: [1, 2, 3 (s, m), 5 (e)]
• Iteration 3: [1, 2, 3, 5 (s, m, e)]
• Iteration 4: [1, 2, 3 (e), 5 (s)] (terminate)
  • e is placed before s.

Example: [1, 3, 5, 7, 9], target = 4

• Iteration 1: [1 (s), 3, 5 (m), 7, 9 (e)]
  • The middle element is greater than the target.
• Iteration 2: [1 (s, m), 3 (e), 5, 7, 9]
• Iteration 3: [1, 3 (s, m, e), 5, 7, 9]
• Iteration 4: [1, 3 (e), 5 (s), 7, 9] (terminate)
  • s is placed after e.

Example: ..., 3, 5, ...; target = 4

• Depending on the remainder of the list, we'll get one of two cases:
  • Case: ..., 3 (s, e), 5, ...
  • Since 3 < 4, s is incremented to point to 5.
  • Case: ..., 3, 5 (s, e), ...
  • Since 5 > 4, e is decremented to point to 3.
• In both cases, s points to the ceiling.

[darwinrlo]

For binary search, use a while loop (as opposed to recursion). The loop condition can be start <= end. end is inclusive.

[darwinrlo]

This pertains to the problem of finding the ceiling of a target element in an array that is sorted in non-decreasing order.

Assume that the target element is not in the array.

Say that the start index is pointing to the element just before the ceiling.

• Every element after the element at the start index is greater than the target element. Hence, the end index will move closer and closer to the ceiling on subsequent iterations. At some point, it will actually land on the ceiling.
• The middle element will then be at the start index, forcing the start index to move up and point to the ceiling.
• The start and end indices now point to the ceiling. The middle element is at the ceiling, which is greater than the target key, forcing the end index to move left past the ceiling. Since the end index is now less than the start index, the algorithm terminates with the start index pointing to the ceiling.

Say the end index has made it to the ceiling.

• Every element to the left of the element at the end index is less than the target element. So the start index will move up closer and closer to the ceiling.
• Eventually, it will land just before the ceiling or on the ceiling itself.
  • If it lands just before the ceiling, it moves to the ceiling on the next iteration.
  • If it lands on the ceiling, the end index moves left on the next iteration, terminating with the start index pointing to the ceiling.

Say the middle element is at some point the ceiling.

• Since the ceiling is greater than the target element, end moves just before the ceiling.
• Since every element between the start and end elements are less than the target element, the start index moves closer and closer to the element just before the ceiling. Eventually, it lands on the element just before the ceiling.
• On the next iteration, the middle element is at the element just before the ceiling, which pushes the start index left past the end index. The algorithm terminates, leaving the the start index on the ceiling.

[darwinrlo]

If finding the floor instead of the ceiling, return the end index instead of the start index.