# Binary Search

### **Problem Statement:-**

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.

**Link:** [https://leetcode.com/problems/binary-search/description/](https://leetcode.com/problems/binary-search/description/)

### **Problem Explanation with examples:-**

**Example 1**

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

**Example 2**

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

### Intuition:-

* Its a sorted array and the best search algo for sorted array is binary search.
    
* Simply find the mid and check if its the target, if not, then reduce the search space by half depending on the target and mid value.
    

### Solution:-

* Initialize l and r to 0 and n-1 respectively.
    
* While l &lt;= r, find the mid by (l+r)//2.
    
* If nums\[mid\] == target, return mid.
    
* If nums\[mid\] &gt; target, then reduce the search space by half by setting r = mid-1.
    
* If nums\[mid\] &lt; target, then reduce the search space by half by setting l = mid+1.
    
* If the target is not found, return -1 after the while loop.
    

### Code:-

JAVA Solution

```java
class Solution {
    public int search(int[] nums, int target) {
        int s=0;
        int e=nums.length-1;
        int m = (s+e)/2;
        while(s<=e){
            m = (s+e)/2;
            if(nums[m] == target)
                return m;
            else if(nums[m] < target)
                s = m+1;
            else{
                e = m-1;
            }
        }
        return -1;
    }
}
```

Python Solution

```java
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l = 0
        r = n-1
        
        while l <= r:
            m = (l+r)//2
            if nums[m] == target:
                return m
            elif nums[m] > target:
                r = m-1
            else:
                l = m+1

        return -1
```

### Complexity Analysis:-

**TIME**:-

The time complexity is **O(logn)** where n is the length of the array nums as we are reducing the search space by half at every step.

**SPACE**:-

The space complexity is **O(1)** as we are not using any extra space.

### References:-

* [**Binary Search**](https://www.geeksforgeeks.org/binary-search/)
    

### Connect with me:-

* [**Twitter**](https://twitter.com/lakshit_cs)
    
* [**Github**](https://github.com/Lakshit-Chiranjiv)
    
* [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)