# Searching

## Linear Search

![Linear/Sequential Search](https://1151231797-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MQAaqgCwmb83T8T0x2j%2Fuploads%2FPjWzwm1tBKbHBnTX3LeN%2Fezgif.com-gif-maker%20\(1\).gif?alt=media\&token=0f98e453-bc45-430b-9694-9c055e7fdcb7)

{% tabs %}
{% tab title="C#" %}
```csharp
int? LinearSearch(int[] array, int target){
    int n = array.Length - 1;
    for(int i = 0; i <= n; i++){
        if(array[i] == target)
            return i;
    }
    return -1;
}
```
{% endtab %}

{% tab title="Python" %}
```python
def linear_search(array, target):
    for i in range(0, len(array)):
        if (array[i] == target):
            return i
    return -1
```
{% endtab %}
{% endtabs %}

| Time Complexity: `O(n)` |
| :---------------------: |

## Binary Search

* Binary search works only on a sorted set of elements.

<div align="center"><img src="https://1151231797-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MQAaqgCwmb83T8T0x2j%2Fuploads%2F1EGwHZzrZIQX5BY9CgmH%2Fezgif.com-gif-maker.gif?alt=media&#x26;token=48c0192c-9cba-4487-9a67-9310b04da2bd" alt="Binary Search"></div>

{% tabs %}
{% tab title="C#" %}
```csharp
int? BinarySearch(int[] array, int target){
    var startIdx = 0;
    var endIdx = array.Length - 1;
    while(startIdx <= endIdx){
        var middleIdx = (startIdx + endIdx) / 2;
        var middleItem = array[middleIdx];
        if(target < middleItem)
            endIdx = middleIdx - 1;
        else if(target > middleItem)
            startIdx = middleIdx + 1;
        else
            return middleIdx;
    }
    return -1;
}
```

* &#x20;Using Recursion:

```csharp
int? RecursiveBinarySearch(int[] array, int target, int low, int high){
    if(low > high)
        return -1;
    
    var middleIdx = (low + high) / 2;
    var middleItem = array[middleIdx];
    if(target < middleItem)
        return RecursiveBinarySearch(array, target, low, middleIdx - 1);
    else if(target > middleItem)
        return RecursiveBinarySearch(array, target, middleIdx + 1, high);
    else
        return middleIdx;
}
```
{% endtab %}

{% tab title="Python" %}
* Using Recursion

```python
def rec_binary_search(array, target, low, high):
    if high >= low:
        mid = low + (high - low) // 2
        if target < array[mid]:
            return rec_binary_search(array, target, low, mid-1) # left half
        elif target > array[mid]:                                   
            return rec_binary_search(array, target, mid + 1, high) # right half
        else:                                                       
            return mid
    else:
        return -1
```
{% endtab %}
{% endtabs %}

| Time Complexity: `O(log n)` |
| :-------------------------: |

{% hint style="info" %}
#### Fact

If all the names in the world are written down together in order and you want to search for the position of a specific name, binary search will accomplish this in a maximum of 35 iterations.
{% endhint %}

{% hint style="success" %}
**Linear Search < Binary Search**
{% endhint %}
