Day1. 704. 二分查找

题目链接：https://leetcode.cn/problems/binary-search/description/

思路：

二分查找：

前提条件：有序不重复元素数组

1.左闭右闭：

定义target在目标数组左闭右闭区间内，[left,right]

if(nums[middle]) > target ，中间元素在目标值的右边，则缩小右边界 right =middle - 1

中间元素在目标值的左边，则左边界 left = middle+1

例如在数组：1,2,3,4,7,9,10中查找元素2，如图所示：

class Solution(object):
    def search(self, nums, target):
       left,right = 0,len(nums)-1
  
       while(left<=right):
        middle = left + (right - left) // 2
        if(nums[middle] > target):
            right = middle - 1
        elif nums[middle] < target:
            left = middle + 1
        else:
            return middle
       return -1

2.左闭又开：

while(left < right ) ，left == right无意义

if(nums[middle] > target) ,right更新为middle ，因为nums[middle] 不等于 target

class Solution(object):
    def search(self, nums, target):
       left,right = 0,len(nums)
       
       while(left<right):
        middle = left + (right - left )//2
        if(nums[middle] > target):
            right = middle
        elif(nums[middle]<target):
            left = middle+1
        else:
            return middle

       return -1