# 这里是二分查找，题目当中 只给出了 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 存在返回下标,我一开始 写成 返回 数值了