# 704. Binary Search

🟩 Easy

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^4`
* `-10^4 < nums[i], target < 10^4`
* All the integers in `nums` are unique.
* `nums` is sorted in ascending order.

## Solution

My Solution

```go
func search(nums []int, target int) int {
    l, r := 0, len(nums)-1
    for l <= r {
        mid := l+(r-l) / 2
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            l = mid+1
        } else {
            r = mid - 1
        }
    }

    return -1
}
```

Optimal Solution (Binary Search)

```go
func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    
    for left <= right {
        mid := left + (right-left)/2  // Prevents integer overflow
        
        switch {
        case nums[mid] == target:
            return mid
        case nums[mid] < target:
            left = mid + 1
        default:
            right = mid - 1
        }
    }
    
    return -1
}
```

### Approach

Binary Search is an efficient algorithm for searching in a sorted array:

1. Initialize pointers:
   * Left pointer at start (index 0)
   * Right pointer at end (index n-1)
2. While left ≤ right:
   * Calculate middle point: mid = left + (right-left)/2
   * Using (right-left)/2 instead of (left+right)/2 prevents integer overflow
3. Compare middle element with target:
   * If equal: found target, return index
   * If target > middle: search right half (left = mid+1)
   * If target < middle: search left half (right = mid-1)
4. If loop ends without finding target:
   * Return -1 (target not found)

### Complexity Analysis

#### Time Complexity: O(log n)

* Each iteration eliminates half of the remaining elements
* The search space is halved in each step
* Takes log₂(n) steps to reduce n elements to 1

#### Space Complexity: O(1)

* Only uses three variables regardless of input size:
  * left - left pointer
  * right - right pointer
  * mid - middle index

### Why it works

* Takes advantage of the sorted nature of the array
* Efficiently eliminates half of the remaining elements in each step
* Using (right-left)/2 prevents integer overflow that could occur with (left+right)/2
* The loop condition left <= right ensures we check all possible elements

![result](/files/TGPUFOcUOObqtZAlWxxC)

Leetcode: [link](https://leetcode.com/problems/binary-search/description/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode.realtemirov.uz/problems/704.-binary-search.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.