LintCode Python 简单级题目 经典二分查找问题

原题描述：

在一个排序数组中找一个数，返回该数出现的任意位置，如果不存在，返回-1

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出数组 [1, 2, 2, 4, 5, 5].

• 对于 target = 2, 返回 1 或者 2.
• 对于 target = 5, 返回 4 或者 5.
• 对于 target = 6, 返回 -1.

挑战：

　　O(logn) 的时间

链接：

　　http://www.lintcode.com/zh-cn/problem/classical-binary-search/

题目分析：

1.给出一个有序数组以及一个目标值target，

2.要求返回target在数组中的位置，若数组里不存在target，则返回-1。

套用经典的二分查找模板即可：

class Solution:
    # @param {int[]} A an integer array sorted in ascending order
    # @param {int} target an integer
    # @return {int} an integer
    def findPosition(self, A, target):
        # Write your code here
        begin = 0
        end = len(A)-1
        n = len(A)
        
        if n == 0:
            return -1
        
        while begin < end:
            mid = begin + (end-begin)/2
            if A[mid] == target:
                return mid
            elif A[mid] < target:
                begin = mid + 1
                end = end
                continue
            else:
                end = mid - 1
                begin = begin
                continue
        
        if A[begin] == target:
            return begin
        if A[end] == target:
            return end
        return -1

题目进阶：

1.给定一个排序的整数数组（升序）和一个要查找的整数target，

2.用O(logn)的时间查找到target第一次出现的下标（从0开始），

3.如果target不存在于数组中，返回-1。

题目分析：

经典问题中返回为target的任意位置，此题变化为要求返回列表中的第一个位置；

沿用经典方案，查找到target的任一位置之后，索引自减，直至target不等于索引值；

返回索引+1即可。

class Solution:
    # @param {int[]} A an integer array sorted in ascending order
    # @param {int} target an integer
    # @return {int} an integer
    def binarySearch(self, A, target):
        # Write your code here
        begin = 0
        end = len(A)-1
        n = len(A)
        
        if n == 0:
            return -1
        
        while begin < end:
            mid = begin + (end - begin)/2
            if A[mid] == target:
                while A[mid] == target:
                    mid = mid - 1
                return mid + 1
            elif A[mid] < target:
                begin = mid + 1
                end = end
                continue
            else:
                end = mid - 1
                begin = begin
                continue
        
        if A[begin] == target:
            return begin
        if A[end] == target:
            return end
        return -1

PS：

　　如果是最后一个位置，索引自增，返回所以-1~