{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# Chapter2 数组与链表、二分查找、大O表示法",
   "id": "b0491b1f5e13e80e"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## 数组的实现",
   "id": "7d180351316303be"
  },
  {
   "cell_type": "code",
   "id": "initial_id",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 定义数组\n",
    "alist = [1,1555,'数据结构',1.2,None,None,None]\n",
    "\n",
    "# 数组按索引查找\n",
    "item1 = alist[0]\n",
    "print(item1)"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "# 数组中插入元素\n",
    "def insert_item(alist,item,pos):\n",
    "    key = len(alist)-1\n",
    "\n",
    "    # 判断数组是否已满\n",
    "    if alist[key] is None:\n",
    "        while key > pos:\n",
    "            # 互换列表内两位置上的元素\n",
    "            alist[key],alist[key-1] = alist[key-1],alist[key]\n",
    "            key -= 1\n",
    "        alist[pos] = item\n",
    "    else:\n",
    "        return '数组已满，无法插入新元素'\n",
    "    return alist\n",
    "\n",
    "# 数组中删除元素\n",
    "def delete_item(alist,pos):\n",
    "    # 删除指定位置的元素\n",
    "    alist[pos] = None\n",
    "\n",
    "    key = pos + 1\n",
    "    item_list = alist[key]\n",
    "    # 前移指定位置后的所有元素\n",
    "    while item_list is not None:\n",
    "        # 互换列表内两位置上的元素\n",
    "        alist[key],alist[key-1] = alist[key-1],alist[key]\n",
    "        key += 1\n",
    "        item_list = alist[key]\n",
    "    return alist"
   ],
   "id": "bf0df34acd72c292",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "insert_item(alist,'Python',1)\n",
    "# delete_item(alist,1)"
   ],
   "id": "bf01446ab84d8ec5",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "## 链表实现",
   "id": "a288a596b7e24c95"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-05-07T07:00:32.006786Z",
     "start_time": "2025-05-07T07:00:31.983022Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# 单链表实现\n",
    "class SingleNode():\n",
    "    # 单链表的结点\n",
    "    def __init__(self,item):\n",
    "        # item存放数据元素\n",
    "        self.item = item\n",
    "        # next是下一个节点的标识\n",
    "        self.next = None\n",
    "\n",
    "class LinkList():\n",
    "    # 单链表\n",
    "    def __init__(self):\n",
    "        self._head = None\n",
    "\n",
    "    def is_empty(self):\n",
    "        \"\"\"判断链表是否为空\"\"\"\n",
    "        return self._head == None\n",
    "\n",
    "    def length(self):\n",
    "        # 链表长度\n",
    "        # cur初始时指向头结点\n",
    "        cur = self._head\n",
    "        count = 0\n",
    "        # 尾结点指向None，当未到达尾部时\n",
    "        while cur != None:\n",
    "            count += 1\n",
    "            # cur后移一个节点\n",
    "            cur = cur.next\n",
    "        return count\n",
    "\n",
    "    def add(self,item):\n",
    "        # 头部添加元素\n",
    "        # 先创建一个保存item值的节点\n",
    "        node = SingleNode(item)\n",
    "        # 将新结点的链接域next指向头结点，即_head指向的位置\n",
    "        node.next = self._head\n",
    "        # 将链表的头_head指向新结点\n",
    "        self._head = node\n",
    "\n",
    "    def append(self,item):\n",
    "        # 尾部添加元素\n",
    "        node = SingleNode(item)\n",
    "        # 先判断链表是否为空，若是空链表，则将_head指向新结点\n",
    "        if self.is_empty():\n",
    "            self._head = node\n",
    "        # 若不为空，则找到尾部，将尾结点的next指向新结点\n",
    "        else:\n",
    "            cur = self._head\n",
    "            while cur.next != None:\n",
    "                cur = cur.next\n",
    "            cur.next = node\n",
    "\n",
    "    def insert(self, pos, item):\n",
    "        \"\"\"指定位置添加元素\"\"\"\n",
    "        # 若指定位置为第一个元素之前，则执行头部插入\n",
    "        if pos <= 0:\n",
    "            self.add(item)\n",
    "        # 若指定位置超过链表尾部，则执行尾部插入\n",
    "        elif pos > (self.length() - 1):\n",
    "            self.append(item)\n",
    "        # 找到指定位置\n",
    "        else:\n",
    "            node = SingleNode(item)\n",
    "            count = 0\n",
    "            # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置\n",
    "            pre = self._head\n",
    "            while count < (pos - 1):\n",
    "                count += 1\n",
    "                pre = pre.next\n",
    "            # 先将新节点node的next指向插入位置的节点\n",
    "            node.next = pre.next\n",
    "            # 将插入位置的前一个节点的next指向新节点\n",
    "            pre.next = node\n",
    "\n",
    "    def remove(self, item):\n",
    "        \"\"\"删除节点\"\"\"\n",
    "        cur = self._head\n",
    "        pre = None\n",
    "        while cur != None:\n",
    "            # 找到了指定元素\n",
    "            if cur.item == item:\n",
    "                # 如果第一个就是删除的节点\n",
    "                if not pre:\n",
    "                    # 将头指针指向头节点的后一个节点\n",
    "                    self._head = cur.next\n",
    "                else:\n",
    "                    # 将删除位置前一个节点的next指向删除位置的后一个节点\n",
    "                    pre.next = cur.next\n",
    "                break\n",
    "            else:\n",
    "                # 继续按链表后移节点\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "\n",
    "    def travel(self):\n",
    "        \"\"\"遍历链表\"\"\"\n",
    "        # 查看元素\n",
    "        cur = self._head\n",
    "        while cur != None:\n",
    "            print(cur.item)\n",
    "            cur = cur.next\n",
    "        print(\"\")"
   ],
   "id": "bb37e59a3243b86c",
   "outputs": [],
   "execution_count": 1
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "# 定义一个链表，加入元素\n",
    "ll = LinkList()\n",
    "ll.add(1)\n",
    "ll.append(1555)\n",
    "ll.append('数据结构')\n",
    "ll.append(1)\n",
    "\n",
    "# 查看元素\n",
    "ll.travel()\n",
    "\n",
    "# 插入元素\n",
    "ll.insert(1,2)\n",
    "ll.travel()\n",
    "\n",
    "# 删除元素\n",
    "ll.remove(2)\n",
    "ll.travel()"
   ],
   "id": "e126388109ec681e",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Q1:判断链表是否有环\n",
    "\n",
    "用多种方式尝试解决这个问题：\n",
    "- 直接遍历，存入哈希表\n",
    "- 快慢指针，Floyd判圈算法"
   ],
   "id": "79c576fde852355f"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "【法一：哈希存储】",
   "id": "86c5b3545ebeab30"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-05-07T07:01:31.593777Z",
     "start_time": "2025-05-07T07:01:31.584056Z"
    }
   },
   "cell_type": "code",
   "source": [
    "def existLoop_hash(LinkList):\n",
    "    \"\"\"哈希法判断链表是否有环\"\"\"\n",
    "    visited = set()\n",
    "    current = LinkList._head\n",
    "    while current:\n",
    "        if current in visited:\n",
    "            return True  # 有环\n",
    "        visited.add(current)\n",
    "        current = current.next\n",
    "    return False  # 无环\n",
    "\n",
    "def findLoopBeginNode_hash(LinkList):\n",
    "    \"\"\"哈希法查找环入口\"\"\"\n",
    "    visited = set()\n",
    "    current = LinkList._head\n",
    "    while current:\n",
    "        if current in visited:\n",
    "            return current  # 当前节点是环入口\n",
    "        visited.add(current)\n",
    "        current = current.next\n",
    "    return None  # 无环"
   ],
   "id": "ef6dd390babc9700",
   "outputs": [],
   "execution_count": 7
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-05-07T07:01:22.486133Z",
     "start_time": "2025-05-07T07:01:22.467122Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# 测试哈希法\n",
    "def test_hash_method():\n",
    "    print(\"===== 测试哈希法 =====\")\n",
    "\n",
    "    # 测试用例1：无环链表\n",
    "    link1 = LinkList()\n",
    "    link1.append(1)\n",
    "    link1.append(2)\n",
    "    link1.append(3)\n",
    "    print(\"链表1（无环）:\")\n",
    "    print(\"existLoop_hash:\", existLoop_hash(link1))  # False\n",
    "    print(\"findLoopBeginNode_hash:\", findLoopBeginNode_hash(link1))  # None\n",
    "    print()\n",
    "\n",
    "    # 测试用例2：单节点自环\n",
    "    link2 = LinkList()\n",
    "    node = SingleNode(1)\n",
    "    link2._head = node\n",
    "    node.next = node  # 自环\n",
    "    print(\"链表2（单节点自环）:\")\n",
    "    print(\"existLoop_hash:\", existLoop_hash(link2))  # True\n",
    "    print(\"findLoopBeginNode_hash:\", findLoopBeginNode_hash(link2).item)  # 1\n",
    "    print()\n",
    "\n",
    "    # 测试用例3：多节点有环（环入口在中间）\n",
    "    link3 = LinkList()\n",
    "    node1 = SingleNode(1)\n",
    "    node2 = SingleNode(2)\n",
    "    node3 = SingleNode(3)\n",
    "    node4 = SingleNode(4)\n",
    "    link3._head = node1\n",
    "    node1.next = node2\n",
    "    node2.next = node3\n",
    "    node3.next = node4\n",
    "    node4.next = node2  # 环入口是节点2\n",
    "    print(\"链表3（多节点有环，入口在中间）:\")\n",
    "    print(\"existLoop_hash:\", existLoop_hash(link3))  # True\n",
    "    print(\"findLoopBeginNode_hash:\", findLoopBeginNode_hash(link3).item)  # 2\n",
    "    print()\n",
    "\n",
    "    # 测试用例4：多节点有环（环入口在头部）\n",
    "    link4 = LinkList()\n",
    "    node1 = SingleNode(1)\n",
    "    node2 = SingleNode(2)\n",
    "    node3 = SingleNode(3)\n",
    "    link4._head = node1\n",
    "    node1.next = node2\n",
    "    node2.next = node3\n",
    "    node3.next = node1  # 环入口是节点1\n",
    "    print(\"链表4（多节点有环，入口在头部）:\")\n",
    "    print(\"existLoop_hash:\", existLoop_hash(link4))  # True\n",
    "    print(\"findLoopBeginNode_hash:\", findLoopBeginNode_hash(link4).item)  # 1\n",
    "    print()\n",
    "\n",
    "    # 测试用例5：无环空链表\n",
    "    link5 = LinkList()\n",
    "    print(\"链表5（空链表）:\")\n",
    "    print(\"existLoop_hash:\", existLoop_hash(link5))  # False\n",
    "    print(\"findLoopBeginNode_hash:\", findLoopBeginNode_hash(link5))  # None\n",
    "    print()"
   ],
   "id": "77c83582af989f9a",
   "outputs": [],
   "execution_count": 5
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-05-07T07:01:25.167234Z",
     "start_time": "2025-05-07T07:01:25.151291Z"
    }
   },
   "cell_type": "code",
   "source": "test_hash_method()",
   "id": "2af899dcf05f44ed",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "===== 测试哈希法 =====\n",
      "链表1（无环）:\n",
      "existLoop_hash: False\n",
      "findLoopBeginNode_hash: None\n",
      "\n",
      "链表2（单节点自环）:\n",
      "existLoop_hash: True\n",
      "findLoopBeginNode_hash: 1\n",
      "\n",
      "链表3（多节点有环，入口在中间）:\n",
      "existLoop_hash: True\n",
      "findLoopBeginNode_hash: 2\n",
      "\n",
      "链表4（多节点有环，入口在头部）:\n",
      "existLoop_hash: True\n",
      "findLoopBeginNode_hash: 1\n",
      "\n",
      "链表5（空链表）:\n",
      "existLoop_hash: False\n",
      "findLoopBeginNode_hash: None\n",
      "\n"
     ]
    }
   ],
   "execution_count": 6
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "【法二：快慢指针】\n",
    "\n",
    "通过快慢指针，可以确定链表中间节点，可用于二分查找等算法\n",
    "\n",
    "只要是质数都可以做快指针，但是走的步数必须小于环。环最小3，所以最好用的就是2"
   ],
   "id": "dc41293aabdd9778"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "# 快慢指针\n",
    "slowNode = LinkList()\n",
    "fastNode = LinkList()\n",
    "\n",
    "while(fastNode != None and fastNode.next != None):\n",
    "    slowNode = slowNode.next\n",
    "    fastNode = fastNode.next.next\n",
    "\n",
    "# 运行至此，各结点情况：\n",
    "# 奇数节点：fastNode为None，slowNode为中间节点\n",
    "# 偶数结点：fast.next为None，slowNode的为前半段最后一个节点"
   ],
   "id": "828360d75fa00670",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "# 判断是否有环\n",
    "def existLoop(LinkList):\n",
    "    if not LinkList._head or not LinkList._head.next:\n",
    "        return False\n",
    "\n",
    "    slow = LinkList._head\n",
    "    fast = LinkList._head\n",
    "\n",
    "    while fast and fast.next:\n",
    "        slow = slow.next\n",
    "        fast = fast.next.next\n",
    "        if slow == fast:\n",
    "            return True\n",
    "    return False"
   ],
   "id": "19b0fc95bb28309d",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "# 判断环入口\n",
    "def findLoopBeginNode(LinkList):\n",
    "    # 链表为空或者只有一个节点时才无环\n",
    "    if not existLoop(LinkList):\n",
    "        return None\n",
    "\n",
    "    slow = LinkList._head\n",
    "    fast = LinkList._head\n",
    "\n",
    "    while fast and fast.next:\n",
    "        slow = slow.next\n",
    "        fast = fast.next.next\n",
    "        if slow == fast:\n",
    "            break # 此时slow和fast在环内相遇\n",
    "\n",
    "    fast = LinkList._head\n",
    "    while slow != fast:\n",
    "        slow = slow.next\n",
    "        fast = fast.next\n",
    "    return slow # or fast"
   ],
   "id": "1af286e353592c76",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "# 测试 existLoop() 和 findLoopBeginNode()\n",
    "def test_linked_list_cycle():\n",
    "    # 测试用例1：无环链表\n",
    "    print(\"=== 测试1：无环链表 ===\")\n",
    "    link1 = LinkList()\n",
    "    link1.append(1)\n",
    "    link1.append(2)\n",
    "    link1.append(3)\n",
    "    print(\"链表元素：1 -> 2 -> 3\")\n",
    "    print(\"existLoop 结果:\", existLoop(link1))  # 应返回 False\n",
    "    print(\"findLoopBeginNode 结果:\", findLoopBeginNode(link1))  # 应返回 None\n",
    "    print()\n",
    "\n",
    "    # 测试用例2：单节点自环\n",
    "    print(\"=== 测试2：单节点自环 ===\")\n",
    "    link2 = LinkList()\n",
    "    node = SingleNode(1)\n",
    "    link2._head = node\n",
    "    node.next = node  # 自环\n",
    "    print(\"链表元素：1 -> 1 (自环)\")\n",
    "    print(\"existLoop 结果:\", existLoop(link2))  # 应返回 True\n",
    "    print(\"findLoopBeginNode 结果:\", findLoopBeginNode(link2).item)  # 应返回 1\n",
    "    print()\n",
    "\n",
    "    # 测试用例3：多节点有环（环入口在中间）\n",
    "    print(\"=== 测试3：多节点有环（环入口在中间） ===\")\n",
    "    link3 = LinkList()\n",
    "    node1 = SingleNode(1)\n",
    "    node2 = SingleNode(2)\n",
    "    node3 = SingleNode(3)\n",
    "    node4 = SingleNode(4)\n",
    "    link3._head = node1\n",
    "    node1.next = node2\n",
    "    node2.next = node3\n",
    "    node3.next = node4\n",
    "    node4.next = node2  # 环入口是节点2\n",
    "    print(\"链表元素：1 -> 2 -> 3 -> 4 -> 2 (环)\")\n",
    "    print(\"existLoop 结果:\", existLoop(link3))  # 应返回 True\n",
    "    print(\"findLoopBeginNode 结果:\", findLoopBeginNode(link3).item)  # 应返回 2\n",
    "    print()\n",
    "\n",
    "    # 测试用例4：多节点有环（环入口在头部）\n",
    "    print(\"=== 测试4：多节点有环（环入口在头部） ===\")\n",
    "    link4 = LinkList()\n",
    "    node1 = SingleNode(1)\n",
    "    node2 = SingleNode(2)\n",
    "    node3 = SingleNode(3)\n",
    "    link4._head = node1\n",
    "    node1.next = node2\n",
    "    node2.next = node3\n",
    "    node3.next = node1  # 环入口是节点1\n",
    "    print(\"链表元素：1 -> 2 -> 3 -> 1 (环)\")\n",
    "    print(\"existLoop 结果:\", existLoop(link4))  # 应返回 True\n",
    "    print(\"findLoopBeginNode 结果:\", findLoopBeginNode(link4).item)  # 应返回 1\n",
    "    print()\n",
    "\n",
    "    # 测试用例5：无环空链表\n",
    "    print(\"=== 测试5：无环空链表 ===\")\n",
    "    link5 = LinkList()\n",
    "    print(\"链表元素：空\")\n",
    "    print(\"existLoop 结果:\", existLoop(link5))  # 应返回 False\n",
    "    print(\"findLoopBeginNode 结果:\", findLoopBeginNode(link5))  # 应返回 None\n",
    "    print()\n",
    "\n",
    "# 运行测试\n",
    "test_linked_list_cycle()"
   ],
   "id": "d1370957db54f4e",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# 二分查找",
   "id": "ca2f4d9ea6a7c1ee"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def sequential_search(alist, item):\n",
    "    \"\"\"利用顺序查找在给定无序数组中查询特定数字\n",
    "    输入：\n",
    "    alist：包含所有待查询数字的list\n",
    "    item：查询的数字\n",
    "    输出：\n",
    "    pos：查询数字在数组中的索引\"\"\"\n",
    "\n",
    "    pos = 0  # 初始化查询位置的索引\n",
    "    while pos < len(alist):\n",
    "        # 如果当前索引的数字等于查询的数字，返回索引\n",
    "        if alist[pos] == item:\n",
    "            return pos, pos+1  # 返回(位置, 比较次数)\n",
    "        # 如果当前数字不等于查询的数字，更新索引\n",
    "        else:\n",
    "            pos += 1\n",
    "    return None, pos  # 未找到时返回None和总比较次数\n",
    "\n",
    "# 初始化数组，生成1-99的奇数\n",
    "alist = [2*i+1 for i in range(0, 50)]\n",
    "\n",
    "# 执行查询并存储结果\n",
    "pos1, epoch1 = sequential_search(alist, 51)\n",
    "pos2, epoch2 = sequential_search(alist, 52)\n",
    "\n",
    "# 打印输出结果\n",
    "print(pos1, epoch1, pos2, epoch2)"
   ],
   "id": "8fd7b3eba932b731",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def order_sequential_search(alist, item):\n",
    "    \"\"\"利用顺序查找在给定有序数组中查询特定数字\n",
    "    输入：\n",
    "    alist: 包含所有待查询数字的list\n",
    "    item: 查询的数字\n",
    "    输出：\n",
    "    pos: 查询数字在数组中的索引\"\"\"\n",
    "\n",
    "    # 初始化查询位置的索引\n",
    "    pos = 0\n",
    "    while pos < len(alist):\n",
    "        # 如果索引在数组中对应的数字等于查询的数字，返回索引\n",
    "        if alist[pos] == item:\n",
    "            return pos, pos\n",
    "        # 如果索引在数组中对应的数字不等于查询的数字，更新\n",
    "        elif alist[pos] > item:  # 有序数组特有优化\n",
    "            return None, pos\n",
    "        else:\n",
    "            pos += 1\n",
    "    return None, pos\n",
    "\n",
    "# 初始化数组，生成1-99的奇数\n",
    "alist = [2*i+1 for i in range(0, 50)]\n",
    "\n",
    "# 查询数组中含有的数字\n",
    "pos1, epoch1 = order_sequential_search(alist, 51)\n",
    "# 查询数组中没有的数字\n",
    "pos2, epoch2 = order_sequential_search(alist, 52)\n",
    "\n",
    "print(pos1, epoch1, pos2, epoch2)"
   ],
   "id": "41824c8474703be3",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Q2:找出最小下标\n",
    "\n",
    "给定一个排好序的数组nums = \\[1, 1, 2, 2, 2, 2, 3, 4, 5, 6, 7, 8]，找到第一个出现所查找数字\n",
    "的下标。如果没有返回-1。"
   ],
   "id": "b2bb9bd77ba5ac54"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def search(list,num):\n",
    "    left , right = 0, len(list)-1\n",
    "    while left+1 < right:\n",
    "        mid = (left+right)//2\n",
    "        if list[mid] >= num:\n",
    "            right = mid\n",
    "        elif list[mid] < num:\n",
    "            left = mid\n",
    "    if list[left] == num:\n",
    "        return left\n",
    "    if list[right] == num:\n",
    "        return right\n",
    "    return -1\n",
    "\n",
    "nums = [1, 1, 2, 2, 2, 2, 3, 4, 5, 6, 7, 8]\n",
    "print(search(nums,2))\n",
    "print(search(nums,12))"
   ],
   "id": "573316dd8d404e5f",
   "outputs": [],
   "execution_count": null
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## Q3:空字符串列表中找下标\n",
    "\n",
    "在一个存在很多空字符串中的列表nums = \\[1, '', 2, '', '', '', '', 3, 4, '', 5, '', 6]中，找到想要找的数的下标"
   ],
   "id": "14d95c6857b6f333"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "source": [
    "def search(nums, n):\n",
    "    \"\"\"在可能包含空字符串的有序列表中查找目标值\n",
    "    参数：\n",
    "        nums: 可能包含空字符串的有序列表\n",
    "        n: 要查找的目标值\n",
    "    返回：\n",
    "        目标值的索引（未找到返回-1）\"\"\"\n",
    "\n",
    "    if len(nums) == 0:\n",
    "        return -1\n",
    "\n",
    "    left = 0\n",
    "    right = len(nums) - 1\n",
    "\n",
    "    while left + 1 < right:\n",
    "        # 跳过右侧空字符串\n",
    "        while left + 1 < right and nums[right] == \"\":\n",
    "            right -= 1\n",
    "        if right < left:\n",
    "            return -1\n",
    "\n",
    "        mid = (right + left) // 2  # 修正为整数除法\n",
    "\n",
    "        # 跳过中间空字符串\n",
    "        while nums[mid] == \"\":\n",
    "            mid += 1\n",
    "\n",
    "        if nums[mid] == n:\n",
    "            return mid\n",
    "        elif nums[mid] < n:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "\n",
    "    # 最终检查左右边界\n",
    "    if nums[left] == n:\n",
    "        return left\n",
    "    if nums[right] == n:\n",
    "        return right\n",
    "\n",
    "    return -1\n",
    "\n",
    "nums = [1, '', 2, '', '', '', '', 3, 4, '', 5, '', 6]\n",
    "print(search(nums,3))"
   ],
   "id": "a41652366bdc122c",
   "outputs": [],
   "execution_count": null
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}