{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [704. 二分查找](https://leetcode.cn/problems/binary-search)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 题目描述 \n",
    "\n",
    "给定一个 `n` 个元素有序的（升序）整型数组 `nums` 和一个目标值 `target`  ，写一个函数搜索 `nums` 中的 `target`，如果 `target` 存在返回下标，否则返回 `-1`。\n",
    "\n",
    "你必须编写一个具有 `O(log n)` 时间复杂度的算法。\n",
    "\n",
    "  \n",
    "**示例 1:**\n",
    "\n",
    "```txt\n",
    "输入: nums = [-1,0,3,5,9,12], target = 9\n",
    "输出: 4\n",
    "解释: 9 出现在 nums 中并且下标为 4\n",
    "```\n",
    "\n",
    "**示例 2:**\n",
    "\n",
    "```txt\n",
    "输入: nums = [-1,0,3,5,9,12], target = 2\n",
    "输出: -1\n",
    "解释: 2 不存在 nums 中因此返回 -1\n",
    "```\n",
    "\n",
    "**提示：**\n",
    "\n",
    "1.  你可以假设 `nums` 中的所有元素是不重复的。\n",
    "2.  `n` 将在 `[1, 10000]`之间。\n",
    "3.  `nums` 的每个元素都将在 `[-9999, 9999]`之间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 解答"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def search(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        left_location, right_location = 0, len(nums) - 1\n",
    "        while left_location <= right_location:\n",
    "            mid_location =   (left_location + right_location) // 2\n",
    "            if nums[mid_location] == target:\n",
    "                return mid_location\n",
    "            elif nums[mid_location] < target:\n",
    "                left_location = mid_location + 1\n",
    "            else:\n",
    "                right_location = mid_location - 1\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6154c8b4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "Solution=Solution().search([5, 6, 7, 8, 9, 10], 6)  # Example usage\n",
    "print(Solution)  # Output: 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6aca97d4",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 5,
 "nbformat_minor": 10
}