> For the complete documentation index, see [llms.txt](https://dailyjournal.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://dailyjournal.gitbook.io/notes/data-structures-and-algorithms/algorithms/searching.md).

# Searching

## Linear Search

![Linear/Sequential Search](/files/vkovqq1TzJIJD1hOaoo6)

{% 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="/files/gBzaze09LP4TaNGhkD19" 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 %}