面试题53：在排序数组中查找数字

题目一：
统计一个数字在排序数组中出现的次数。

思路：
这道题需要利用二分查找法，如果直接遍历查找很简单，但是这样时间效率不高，要分析更简单的思路，因为是排序的数组，想到可以使用二分查找法，首先一个函数找到k的开始位置，另一个找到k的结束位置，然后相减即可。这样复杂度是两个O(logn)相加，还是O(logn)，效率提高，具体思路如下：

53 排序数组中查找某个数字.png

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        number = 0
        if data != None and len(data)>0:
            first = self.FindFirst(data, len(data), k, 0, len(data)-1)
            last = self.FindEnd(data,len(data), k, 0, len(data)-1)
            if first >-1 and last >-1:
                number = last - first+1
        return number
    def FindFirst(self, data, length, k, start, end):
        #没有找到k
        if start > end:
            return -1
        midIndex = (start+end)//2 
        midvalue = data[midIndex]

        if midvalue ==k:
            if midIndex == 0 or (midIndex > 0 and data[midIndex-1] !=k):
                return midIndex
            else:
                end = midIndex-1  #k的第一个位置还在前面

        elif midvalue >k:
            end = midIndex-1

        else:
            start = midIndex+1

        return self.FindFirst(data, length, k, start,end)

    def FindEnd(self, data, length, k, start, end):
        #没有找到k
        if start > end:
            return -1
        midIndex = (start+end)//2 
        midvalue = data[midIndex]

        if midvalue ==k:
            if midIndex == length-1 or (midIndex < length-1 and data[midIndex+1] !=k):
                return midIndex
            else:
                start = midIndex+1  #k的最后一个位置还在后面

        elif midvalue >k:
            end = midIndex-1

        else:
            start = midIndex+1
        
        return self.FindEnd(data, length, k, start,end)

提交结果：

题目二：寻找缺失的数字
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

思路：
遍历序列求出和，然后计算得出0-n的结果，二者的差值就是缺失的那个数字。

代码实现：

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #差值法
        Numsum = 0
        for i in range(len(nums)):
            Numsum += nums[i]
        sumN = (0 + len(nums))*(len(nums)+1)/2
        return sumN-Numsum

思路二：
假设这个数组是递增的有序数组，那么只需要使用二分查找的方法查找，题目可以转换为查找下标与对应元素不同的第一个位置，缺失的就是这个位置索引。

代码实现二：

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
       """
        #二分查找法
        nums.sort()
        index =-1
        left = 0
        right = len(nums)-1
        while(left <= right and left >=0 and right >=0):
            middle = (left+right)//2
            if nums[middle] != middle:
                if middle ==0 or nums[middle-1] == middle-1:
                    index = middle
                    break
                else:
                    right = middle-1
            else:
                left = middle+1
        if left == len(nums):
            index = left
        return index

提交结果：