欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【LintCode-二分搜索】457. ClassicalBinarySearch

程序员文章站 2022-05-13 19:58:09
...

lintcode 457. Classical Binary Search

url: https://www.lintcode.com/problem/classical-binary-search/description

1、题目

Description
Find any position of a target number in a sorted array. Return -1 if target does not exist.
Have you met this question in a real interview?
Example

Example 1:
Input: nums = [1,2,2,4,5,5], target = 2
Output: 1 or 2

Example 2:
Input: nums = [1,2,2,4,5,5], target = 6
Output: -1

Challenge
O(logn) time

2、思路

经典的二分搜索

3、python代码实现

# -*- coding: utf-8 -*-
class Solution:
    """
    @param nums: An integer array sorted in ascending order
    @param target: An integer
    @return: An integer
    """

    def findPosition(self, nums, target):
        head = 0
        tail = len(nums) - 1
        mid = len(nums) // 2
        if not nums:
            return -1
        if nums[head] > target or nums[tail] < target:
            return -1

        while head < tail:
            if nums[mid] < target:
                head = mid + 1
            elif nums[mid] > target:
                tail = mid - 1
            else:
                return mid
            mid = head + (tail - head)//2
        return -1


if __name__ == '__main__':
    s = Solution()
    nums = [1, 2, 2, 4, 5, 5]
    print(s.findPosition(nums, 2))
    print(s.findPosition(nums, 6))
    print(s.findPosition([], 6))
相关标签: 二分搜索