Binary Search in C#
Tags: webdev, csharp, algorithms, datastructures
Published: 2023-10-26 12:58:46


Hi Everyone,

Today, we will be solving Leetcode question [704](https://leetcode.com/problems/binary-search/description/) - Binary Search, in C#

This article will not only show you how to solve this famous question in C# but it will also expose you to the concept of Binary Search as a whole.

Let's Dive in.

**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**

This seems like a pretty straightforward question but then the caveat of solving in O(log n) time complexity comes into play.

First, we need to answer the question,  What is Binary Search? 
According to Khan Academy, Binary search is an efficient algorithm for finding an item from a sorted list of items. **It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one.**

With this in mind, let's try to solve the question

The first thing we need to do is initialize our variables, we will need 3 variables, a low pointer, a high pointer and middle pointer(the division of the sum of the low and high by 2)

```csharp
int low =0, high = nums.Length - 1, mid = (low + high)/2;
```

Next, we Introduce our conditional while statement that will only run while the value of our low pointer is less than or equal to our high

```csharp
while(low <= high){
```

Now, in our loop we first check that the value of our array at position mid is equal to the target we are looking for, if it is, just return the value of mid, since we have found our answer

```csharp
 if(nums[mid] == target) return mid;
```

The next condition is to check that the value of our array at position mid is greater than our target, if it is, we simply reassign our high variable to be the value of our mid variable minus 1

```csharp
 if(nums[mid] > target) high = mid -1;
```

Of course in the same vain, we check that the value of our array at position mid is less than our target, if it is, we simply reassign our low variable to be the value of our mid variable plus 1

```csharp
if(nums[mid] < target) low = mid + 1;
```

Then finally, we compute a new mid using either of the low or high variables that would've changed

```csharp
mid= (low + high)/2;
```

Finally, we close our while loop and return something if we don't find our target in the while loop. The question states that we return -1 so we'll do that.

Putting it all together, your solution should look like this

```csharp
public int Search(int[] nums, int target) {
        int low =0, high = nums.Length - 1, mid = (low + high)/2;
        while(low <= high){
            if(nums[mid] == target) return mid;
            if(nums[mid] > target) high = mid -1;
            if(nums[mid] < target) low = mid + 1;
            mid= (low + high)/2;
        }
        return -1;
    }
```

Thanks for reading, I look forward to solving more Leetcode( and general Algorithmic) problems using C# in the future. Happing coding.