# Binary Seach 

Imagine you’re searching for a word in a dictionary.  
You don’t start from page 1, right?  
You open somewhere in the middle.

*   If your word comes before → go left
    
*   If it comes after → go right
    

This is exactly how **Binary Search** works.

* * *

### Core Idea of Binary Search

**Instead of checking every element (like linear search), we:**

*   Pick the **middle element**
    
*   Compare with target
    
*   Eliminate half of the search space
    

* * *

### Basic Binary Search Formula

```js
mid = (Left + right) / 2
```

**Decision Making**

Once we calculate `mid`, we compare:

*   If `arr[mid] == target`  
    → Target found
    
*   If `arr[mid] > target`  
    → Target lies on the **left side**  
    → Move:
    
    ```plaintext
    right = mid - 1;
    ```
    
*   If `arr[mid] < target`  
      
    → Target lies on the **right side**  
      
    → Move:
    
    ```plaintext
    left = mid + 1;
    ```
    

* * *

### Problem Statement:

Given a **sorted array** of size `n` and an integer `target`, determine whether the target exists in the array.

If the target is present, return its **index (0-based)**.  
If the target is not present, return **\-1**.

* * *

### S**tep-by-Step Dry Run**

Let’s say you have an array:

```plaintext
[3, 5, 2, 1, 4]
 0  1  2  3  4
```

First rule:

> Binary Search only works on a **sorted array**

So we sort it:

```plaintext
[1, 2, 3, 4, 5]
 0  1  2  3  4
```

**Now Search Target = 4**

**Step 1:**

```plaintext
[1, 2, 3, 4, 5]
 0  1  2  3  4
 l     m     r
           
```

*   mid = 2 → value = 3
    
*   4 > 3 → ignore left half
    
*   Move right: l = 3
    

**Step 2:**

```plaintext
[1, 2, 3, 4, 5]
 0  1  2  3  4
          m  r
          l
```

*   mid = 3 → value = 4
    
*   Found!
    

* * *

### Code

```javascript
int l = 0, r = n - 1;

while (l <= r) {
    int mid = (l + r) / 2;

    if (arr[mid] == target) {
        return mid; // found
    } else if (arr[mid] < target) {
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}

return -1; // not found
```

* * *

### Complexity

*   **Time Complexity:** `O(log n)`
    
*   **Space Complexity:** `O(1)`
    

* * *

### Where This Pattern is Used

This is where things get interesting 👇

The same binary search logic helps solve multiple problems:

1.  **First & Last Occurrence**
    
2.  **Frequency of an Element**
    
3.  **Count of Elements Greater Than X**
    
4.  **Count of Elements Between X and Y**
    

> Once you understand pointer movement, all these problems become easy.