二分搜索

二分搜索提醒：
取得中点写法：

常规写法：mid=(left+right)/2

由于上述写法可能造成溢出，更安全的写法：mid=left+(right-left)/2

案例一：对于一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。

给定一个数组arr及它的大小n，同时给定num。请返回所求位置。若该元素在数组中未出现，请返回-1。

# -*- coding:utf-8 -*-

class LeftMostAppearance:
    def findPos(self, arr, n, num):
        # write code here
        if not arr:
            return -1
        left = 0
        right = n-1
        while left<right:
            mid = left+(right-left)/2
            # 由于取的是下限，为保证最后能和right指针重合，所以当小于时需要多移动一位
            if arr[mid]<num:
                left = mid+1
            # 同样为了保证left和right重合，需要在arr[mid]>=num时（注意等号）将mid直接赋给right
            if arr[mid]>=num:
                right = mid
         # 最后得到的就是最左边等于num的数字。
        if arr[left] != num:
            return -1
        return left