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