> For the complete documentation index, see [llms.txt](https://private-26.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://private-26.gitbook.io/notes/coding/easy/704.-binary-search.md).

# 704. Binary Search

## Intitution

Given a **sorted array**, and we need to find the index of a `target` element efficiently.

Since the array is sorted in **ascending order**, we can use **Binary Search**, which divides the array in half every time, reducing time complexity from $$\text{O}(n)$$ to $$\text{O}(n\log{n})$$

## Complexity

| Space Complexity | Time Complexity        |
| ---------------- | ---------------------- |
| $$\text{O}(1)$$  | $$\text{O}(n\log{n})$$ |

## Code

```java
public int search(int[] nums, int target) {
    
    // Edge case: only one element
    if (nums.length == 1) return nums[0] == target ? 0 : -1;

    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = (left + right) >> 1; // Efficient way to get mid = (left + right) / 2

        if (nums[mid] == target) return mid; // Found target

        if (nums[mid] > target) {
            right = mid - 1; // Target is in the left half
        } else {
            left = mid + 1; // Target is in the right half
        }
    }

    return -1; // Target not found
}
```