# Binary Search
**Difficulty:** EASY
[External](https://leetcode.com/problems/binary-search)
Canonical: https://scaleengineer.com/dsa/problems/binary-search
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Cognizant](https://scaleengineer.com/companies/cognizant), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Infosys](https://scaleengineer.com/companies/infosys), [Wipro](https://scaleengineer.com/companies/wipro), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs)
---
## Problem
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 <= 104`
* `-104 < nums[i], target < 104`
* All the integers in `nums` are **unique**.
* `nums` is sorted in ascending order.

# Approaches
## Linear Search (Brute Force)
The most straightforward approach is to iterate through each element of the array and check if it matches the target. This method does not take advantage of the sorted nature of the array.
**Time:** O(n) - In the worst-case scenario, we might have to scan the entire array of size 'n' to find the target or determine it's not present. · **Space:** O(1) - We only use a constant amount of extra space for variables like the loop counter.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large datasets as it doesn't utilize the sorted property of the array.; Fails to meet the O(log n) time complexity requirement of the problem.
### Explanation
This brute-force method involves a simple loop that traverses the array from the first element to the last. In each iteration, we compare the current element with the `target` value. If the current element is equal to the `target`, we have found our element, and we return its index. If the loop completes without finding the `target`, it means the target is not present in the array, so we return -1.

```java
class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}
```
### Algorithm
- Iterate through the array `nums` from index `i = 0` to `nums.length - 1`.
- For each element `nums[i]`, compare it with `target`.
- If `nums[i] == target`, return the index `i`.
- If the loop finishes, it means the target was not found. Return `-1`.

## Recursive Binary Search
A more efficient approach that leverages the sorted property of the array is binary search. This can be implemented recursively. The core idea is to repeatedly divide the search space in half.
**Time:** O(log n) - With each recursive call, the size of the search space is halved. The number of times you can halve 'n' until you get to 1 is log₂(n). · **Space:** O(log n) - This is due to the recursion call stack. In the worst case, the depth of the recursion can be log n, consuming space on the stack for each function call.
**Pros:** Achieves the required O(log n) time complexity.; Code can be more concise and closer to the mathematical definition of the algorithm for some developers.
**Cons:** Uses extra space for the recursion stack, which can lead to a stack overflow error for very large arrays (though not an issue with the given constraints).; Slightly less space-efficient than the iterative version.
### Explanation
This approach uses a helper function that takes the array, target, and the current search boundaries (`left` and `right`) as arguments. The base case for the recursion is when the `left` pointer crosses the `right` pointer (`left > right`), indicating the target is not in the array. In each recursive call, we calculate the middle index. If the middle element is the target, we return its index. If the target is larger than the middle element, we discard the left half and make a recursive call on the right half. If the target is smaller, we discard the right half and make a recursive call on the left half.

```java
class Solution {
    public int search(int[] nums, int target) {
        return binarySearchRecursive(nums, target, 0, nums.length - 1);
    }

    private int binarySearchRecursive(int[] nums, int target, int left, int right) {
        if (left > right) {
            return -1; // Base case: target not found
        }

        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            return binarySearchRecursive(nums, target, mid + 1, right);
        } else {
            return binarySearchRecursive(nums, target, left, mid - 1);
        }
    }
}
```
### Algorithm
- Define a recursive helper function `searchHelper(nums, target, left, right)`.
- **Base Case:** If `left > right`, the search space is empty. Return `-1`.
- Calculate the middle index: `mid = left + (right - left) / 2`.
- If `nums[mid] == target`, return `mid`.
- If `nums[mid] < target`, the target must be in the right half. Return `searchHelper(nums, target, mid + 1, right)`.
- If `nums[mid] > target`, the target must be in the left half. Return `searchHelper(nums, target, left, mid - 1)`.
- The initial call from the main function will be `searchHelper(nums, target, 0, nums.length - 1)`.

## Iterative Binary Search
This is the most optimal and common implementation of binary search. It achieves the same logarithmic time complexity as the recursive version but without the overhead of the recursion stack, making it more space-efficient.
**Time:** O(log n) - The search interval is halved in each iteration of the loop. This logarithmic time complexity is highly efficient for large datasets. · **Space:** O(1) - This approach uses a constant amount of extra space for the `left`, `right`, and `mid` pointers, regardless of the input array size. This makes it the most space-efficient solution.
**Pros:** Optimal time complexity of O(log n).; Optimal space complexity of O(1).; Avoids the risk of stack overflow associated with recursion.
**Cons:** Slightly more complex to write than a simple linear search, with potential for off-by-one errors if not implemented carefully.
### Explanation
We initialize two pointers, `left` to the start of the array and `right` to the end. We enter a `while` loop that continues as long as our search space is valid (`left <= right`). Inside the loop, we calculate the middle index. It's important to use `mid = left + (right - left) / 2` to prevent potential integer overflow. We compare the middle element with the target. If they match, we return the middle index. If the target is greater than the middle element, we know the target must be in the right half, so we move our `left` pointer to `mid + 1`. If the target is smaller, it must be in the left half, so we move our `right` pointer to `mid - 1`. If the loop terminates, it means `left` has become greater than `right`, and the target was not found. We return -1.

```java
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            // Prevent (left + right) overflow
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // Target is not in the array
        return -1;
    }
}
```
### Algorithm
- Initialize two pointers: `left = 0` and `right = nums.length - 1`.
- Loop as long as `left <= right`.
- Calculate the middle index: `mid = left + (right - left) / 2`.
- If `nums[mid] == target`, the element is found. Return `mid`.
- If `nums[mid] < target`, the target is in the right half. Update `left = mid + 1`.
- If `nums[mid] > target`, the target is in the left half. Update `right = mid - 1`.
- If the loop ends, the target is not in the array. Return `-1`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left] == target ? left : -1;
    }
}
```

### Java

```java
class Solution {
public
  int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] >= target) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return nums[left] == target ? left : -1;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} target * @return {number} */ var search =
  function (nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (nums[mid] >= target) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return nums[left] == target ? left : -1;
  };

```

### CPP

```cpp
class Solution {
public:
  int search(vector<int> &nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
      int mid = left + right >> 1;
      if (nums[mid] >= target)
        right = mid;
      else
        left = mid + 1;
    }
    return nums[left] == target ? left : -1;
  }
};

```

### Python

```python
class Solution:
    def search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left < right: mid = (left + right) >> 1 if nums[mid] >= target: right = mid else: left = mid + 1 return left if nums[left] == target else - 1

```