LintCode 457 [Classical Binary Search]

原题

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

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

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

解题思路

• 标准的二分法解决 - Binary Search 模板程序

完整代码

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
        if A is None or A == []:
            return -1
        
        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if A[mid] == target:
                return mid
            elif A[mid] > target:
                end = mid
            else:
                start = mid
            
        if A[start] == target:
            return start
        if A[end] == target:
            return end
        return -1