Binary Search in C#

#webdev #csharp #algorithms #datastructures

Hi Everyone,

Today, we will be solving Leetcode question 704 - 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)

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

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

 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

 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

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

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

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;
    }