Перейти к содержанию

Binary Search

🇷🇺 Название: Бинарный поиск
LeetCode: binary-search
Временная сложность: O(log n)
Пространственная сложность: O(1)

Решение

from typing import List


class Solution:  
    def search(self, nums: List[int], target: int) -> int:  
        left = 0  
        right = len(nums) - 1  

        while left <= right:  
            middle = left + (right - left) // 2  

            if target > nums[middle]:  
                left = middle + 1  
            elif target < nums[middle]:  
                right = middle - 1  
            else:  
                return middle  
        return -1

🇺🇸 Условие

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

🇷🇺 Условие

Примеры

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

{
  "examples": [
    {
      "input": {
        "nums": [-1,0,3,5,9,12],
        "target": 9
      },
      "output": 4
    },
    {
      "input": {
        "nums": [-1,0,3,5,9,12],
        "target": 2
      },
      "output": -1
    }
  ]
}

Ограничения

  • \(1 \leq nums.length \leq 10^4\)
  • \(-10^4 < nums[i], target < 10^4\)
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Потребление ресурсов

⏱ Time complexity: O(log n)

  • На каждом шаге диапазон поиска уменьшается в 2 раза.
  • Всего будет максимум log₂(n) итераций.

Итог: O(log n)

🧠 Space complexity: O(1)

  • Используются только 3 переменные: left, right, middle.
  • Без рекурсии и дополнительных структур.

Итог: O(1)

easy array binary-search


Metadata

  • title_rus: Бинарный поиск
  • difficulty: Easy
  • leetcode_url: https://leetcode.com/problems/binary-search/
  • topics: ['Array', 'Binary Search']
  • time: O(log n)
  • space: O(1)
  • grind75: True
  • tags: ['Array', 'Binary Search', 'Easy', 'problem']
  • git_revision_date_localized: 5 июля 2025 г.
  • git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
  • git_revision_date_localized_tag:
  • git_revision_date_localized_raw_date: 5 июля 2025 г.
  • git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
  • git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
  • git_revision_date_localized_raw_iso_date: 2025-07-05
  • git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
  • git_revision_date_localized_raw_timeago:
  • git_revision_date_localized_raw_custom: 05. июля 2025
  • git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
  • git_site_revision_date_localized_tag:
  • git_site_revision_date_localized: 5 июля 2025 г.
  • git_site_revision_date_localized_raw_date: 5 июля 2025 г.
  • git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
  • git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
  • git_site_revision_date_localized_raw_iso_date: 2025-07-05
  • git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
  • git_site_revision_date_localized_raw_timeago:
  • git_site_revision_date_localized_raw_custom: 05. июля 2025