【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))
上一篇: 读 山 行