:orphan:

Binary Search
=============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/binary-search/

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

**Constraints:**

- ``1 <= nums.length <= 10``\ :sup:```4```
- ``-10``\ :sup:```4```\ ``< nums[i], target < 10``\ :sup:```4```
- All the integers in ``nums`` are **unique**.
- ``nums`` is sorted in ascending order.

.. highlight:: python

Pattern
-------
Array, Binary Search

Approaches
----------

.. tab-set::

    .. tab-item:: Iterative

        **Code**

        .. literalinclude:: ../problems/easy/binary-search/binary_search__iterative.py
            :language: python
            :lines: 10-

        **Test**

        >>> from binary_search__iterative import search
        >>> search([-1, 0, 3, 5, 9, 12], 9)
        4
        >>> search([-1, 0, 3, 5, 9, 12], 2)
        -1

        .. autofunction:: binary_search__iterative.search