{
  "schema_version": 1,
  "prompt": {
    "type": "doc",
    "blocks": [
      {
        "type": "paragraph",
        "content": [
          {
            "type": "text",
            "text": "The function below is meant to return the index of target in the sorted list items, or -1 if it is absent. It usually works — but it has a bug. Fix it so that every test passes."
          }
        ]
      },
      {
        "type": "code_block",
        "language": "python",
        "code": "def binary_search(items, target):\n    lo, hi = 0, len(items) - 1\n    while lo < hi:\n        mid = (lo + hi) // 2\n        if items[mid] == target:\n            return mid\n        elif items[mid] < target:\n            lo = mid + 1\n        else:\n            hi = mid - 1\n    return -1\n"
      }
    ]
  },
  "answer": {
    "type": "code",
    "language": "python",
    "entry_point": "binary_search",
    "starter_code": "def binary_search(items, target):\n    lo, hi = 0, len(items) - 1\n    while lo < hi:\n        mid = (lo + hi) // 2\n        if items[mid] == target:\n            return mid\n        elif items[mid] < target:\n            lo = mid + 1\n        else:\n            hi = mid - 1\n    return -1\n",
    "tests": [
      {
        "name": "finds an interior element",
        "input": { "args": [[1, 3, 5, 7, 9], 7] },
        "expected": 3
      },
      {
        "name": "returns -1 for a missing element",
        "input": { "args": [[1, 3, 5, 7, 9], 4] },
        "expected": -1
      },
      {
        "name": "handles the empty list",
        "input": { "args": [[], 1] },
        "expected": -1
      },
      {
        "name": "finds the only element of a singleton list",
        "input": { "args": [[2], 2] },
        "expected": 0
      },
      {
        "name": "finds the last element",
        "input": { "args": [[1, 3, 5, 7, 9], 9] },
        "expected": 4
      }
    ],
    "time_limit_ms": 2000,
    "memory_limit_mb": 64
  },
  "hints": [
    {
      "type": "doc",
      "blocks": [
        {
          "type": "paragraph",
          "content": [
            {
              "type": "text",
              "text": "Trace the function by hand on binary_search([2], 2). How many times does the loop body run?"
            }
          ]
        }
      ]
    },
    {
      "type": "doc",
      "blocks": [
        {
          "type": "paragraph",
          "content": [
            {
              "type": "text",
              "text": "With an inclusive upper bound (hi = len(items) - 1), the search interval [lo, hi] still contains one candidate when lo == hi. Look closely at the loop condition."
            }
          ]
        }
      ]
    }
  ],
  "solution": {
    "type": "doc",
    "blocks": [
      {
        "type": "paragraph",
        "content": [
          {
            "type": "text",
            "text": "Because hi is an inclusive bound, the interval [lo, hi] is non-empty exactly while lo <= hi. The buggy condition lo < hi stops one iteration early and never inspects the final candidate, so singleton lists and last-position targets fail. The fix is a single character:"
          }
        ]
      },
      {
        "type": "code_block",
        "language": "python",
        "code": "def binary_search(items, target):\n    lo, hi = 0, len(items) - 1\n    while lo <= hi:\n        mid = (lo + hi) // 2\n        if items[mid] == target:\n            return mid\n        elif items[mid] < target:\n            lo = mid + 1\n        else:\n            hi = mid - 1\n    return -1\n"
      },
      {
        "type": "paragraph",
        "content": [
          {
            "type": "text",
            "text": "An equivalent fix is the half-open convention: hi = len(items), loop while lo < hi, and shrink with hi = mid. Either is correct — the bug was mixing the two conventions."
          }
        ]
      }
    ]
  }
}