Leetcode704 二分查找（数组）
# 这里是二分查找，题目当中 只给出了 n个 升序 整型 数组nums，目标变量名称是 target，
# 要求 存在返回 下标，不存在 返回 -1，时间复杂度O(logn)
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
#首先 ，一开始我想着 用 left < right 去定义 边界 当满足 条件 进入 循环 去 查找 target
# 但是 这样的话 会 出现 到底 能不能left == right 呢
# 所以 因为数组 是个什么样子的，开 闭不知道 ，并未 明确说明 四种 情况，
# 考虑 左闭右闭，左闭右开，或者 左开右闭，或者 左开右开
# 然后 思考 正是 因为 由于 数组条件不确定 造成的 代码中 两个 判断 不同点 主要 是 在
# 1. 到底 能不能left == right
# 2. 边界 要不要 等于 中间 索引 呢
#所以 这里 我们 分情况 讨论
# 然后 二分 查找 需要 表示 中间值，一开始 我想着 用left right 表示 具体的 值，但是这样 后面 会 边界移动
# 所以 应该是 left right 表示 索引，利用 索引 取值
# todo 1. 假设 是 左闭右闭
# 可以 等于， 当 left <= right时，while循环 直到 找到 符合 条件的 ，否则 找不到返回 -1
#之所以 while 因为 要一直 迭代 并不知道 具体次数
while left <= right:
mid = left + (right - left) // 2
if target==nums[mid]:
return mid
elif target<nums[mid]:
right = mid -1
# 因为 我们已经判断了 目标值 小于 中间值 ，那么 移动 右边界
# 要不要 取到 中间的 数 呢 因为 是闭区间，中间的值 不是 我们 想要的 所以 不取
# 直接 再往左 取到 左边的 一个数 即可
else :
left= mid + 1
return -1
# todo 2. 假设 左闭 右 开
class Solution(object):
def search(self, nums, target):
left, right = 0, len(nums)
#这里 左闭 右开 如果 left=right 与题目 相悖
while left < right:
mid = left + (right - left) // 2
if target==nums[mid]:
return mid
elif target<nums[mid]:
right=mid
# 因为是开区间,我们的目标值 在左侧 ，右边 开区间 ，取不到 右边的值 同时 中间 索引的 值 不是 我们想要的
# 所以 直接 右边界 等于 中间的 索引 即可
# 如果 往左 一个数 又是 开区间 取不到 相当于 我们 把 左一个的数 丢掉了
else :
left=mid + 1
return -1
# # 犯错点
# 1. 边界条件，当区间 开闭不同 时 用于 表示 索引的 数值 不同
# 2.不能用 固定的 字母 表示 数组 中的 数字 因为 要考虑 边界 的 移动 数字 在 不断 变换
# 3.如果 target 存在返回下标,我一开始 写成 返回数值了