# 0704. Binary Search

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Binary Search](https://leetcode.com/problems/binary-search/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0704-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.**
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

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

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

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

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Standard **Binary Search** Problem.
{% endhint %}

#### **Boundary / Search Space**

> Left (Minimum) = 0\
> Right (Maximum) = len(array) **(last element could be the answer)**

#### **Condition**

> While Loop = Left < Right\
> Return = array\[mid] == target number

#### **Return Value**

> Index or -1 (not found)
> {% endtab %}
> {% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # (base case)
        if len(nums) == 1: return 0 if nums[0] == target else -1
        
        # ==================================================
        #  Array + Binary Search                           =
        # ==================================================
        # time  : O(log(n))
        # space : O(1)

        l, r = 0, len(nums)
        while l < r:
            mid = (l + r) // 2
            
            if nums[mid] == target: return mid
            elif nums[mid] > target: r = mid
            elif nums[mid] < target: l = mid + 1
                
        return -1
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(log(n))
     * @space : O(1)
     */
    
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        
        while(left < right) {
            int mid = (left + right) / 2;
            
            if(nums[mid] == target) {
                return mid;
                
            } else if(nums[mid] > target) {
                right = mid;
                
            } else if(nums[mid] < target) {
                left = mid + 1;
            }
        }
        
        return -1;
    }
}
```

{% endtab %}
{% endtabs %}