135 lines
3.1 KiB
Plaintext
135 lines
3.1 KiB
Plaintext
{
|
||
"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
|
||
}
|