3.2 First Position of Target

在线题测：https://www.lintcode.com/problem/first-position-of-target/description

在线题解：https://www.jiuzhang.com/solution/first-position-of-target/

14.二分查找

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

样例

样例  1:
    输入:[1,4,4,5,7,7,8,9,9,10]，1
    输出: 0

    样例解释: 
    第一次出现在第0个位置。

样例 2:
    输入: [1, 2, 3, 3, 4, 5, 10]，3
    输出: 2

    样例解释: 
    第一次出现在第2个位置

样例 3:
    输入: [1, 2, 3, 3, 4, 5, 10]，6
    输出: -1

    样例解释: 
    没有出现过6， 返回-1

挑战

如果数组中的整数个数超过了2^32，你的算法是否会出错？

更新的代码

class Solution:
    # @param nums: The integer array
    # @param target: Target number to find
    # @return the first position of target in nums, position start from 0 
    def binarySearch(self, nums, target):
        # write your code here
        if nums is None :
            return -1

        start, end = 0, len(nums) - 1
        while start + 1 < end :
            mid =(start + end ) / 2
            if nums[mid] == target :
                end = mid
            elif nums[mid] < target:
                start = mid
            else:
                end = mid

        if nums[start] == target :
            return start
        if nums[end] == target :
            return end
        return -1

Jave版参考：https://www.jiuzhang.com/solution/first-position-of-target/

源码分析参考：http://www.code123.cc/docs/leetcode-notes/binary_search/binary_search.html

九章分析源码分析 （下面是九章算法提供二分查找的模板） 四个要点：

要点1：while终止条件应为start + 1 < end （据说这个是最好的判断）而不是start <= end，start == end时可能出现死循环。即循环终止条件是相邻或相交元素时退出。九章介绍图如下：【九章分析】为什么不写 while(start < end )

假设start=1， end =2
while (start <end)
{
mid=(start+end)/2 
 start=mid  
} 

循环1： mid=(1+2)/2=1,start=1
循环2： mid=(1+1)/=1, start=1
循环3： mid=(1+1)/=1, start=1
循环4： mid=(1+1)/=1, start=1
.....
循环N： mid=(1+1)/=1, start=1 (死循环）

要点2：迭代终止时target应为start或者end中的一个——由上述循环终止条件有两个，具体谁先谁后视题目是找 first position or last position 而定。

【九章分析】配合刚才的while循环中的 start+1<end,也就是start和end是相邻的，
我们也不知道start 和target哪个是我们要找的target,所以我们就用下面的判断
如果是start是我们要找到 target，那就返回start的值；如果end是我们要找到，
那就返回 end要找的值；如果都不是，就返回-1

if array[start] == target:
return start
if array[end] == target:
return end
return -1

要点3： while循环中的语句都没有+1 或者 -1，九章说这是为了省脑细胞。因为总是分不清+1 和-1。配合while终止条件start + 1 < end（相邻即退出）的赋值语句mid永远没有+1或者-1，这样不会死循环。

要点4： 为什么写成mid = start + (end - start) / 2，这是防止溢出的。九章说“装B“ ，这是为了告诉面试官这个地方考虑溢出。实际上一个数值不会巨大
到2的32次方，所以溢出的概率为0。值得注意的是，python 是高精度的，不会溢出。 Java和C++有溢出问题。