Post
Ask Question

Binary Search With C#

Introduction

 
A very common Search Algorithm is the Binary Search Tree, which will search the list by dividing it until the match is found. Its Big O is Log n.
 
How it works
 
Ah!! It functions by dividing the list in half or creating the list in two parts in every iteration.
 
Steps what it follows,
 
It will first find a median in the list and then compare the target value.
 
If the value is smaller which means the Left side of the median.
 
If the target is greater than the median it will search the Right side of the median.
 
What if the value is exactly at the median??
 
Ha Ha.. you got the point!
 
It will keep on breaking the list into half unless the median is not the target.
 
If there is no match, this means that the list is now unbreakable and the value is not found. It returns.
 
Let's understand this by Code.
 
(Recursion)
  1. public int BinarySearch(int[] nums, int start, int end, int target) {  
  2.     int median = ((start + end) / 2);  
  3.     if (start > end) {  
  4.         return -1;  
  5.     }  
  6.     if (nums[median] == target) {  
  7.         return median;  
  8.     } else if (nums[median] < target) {  
  9.         BinarySearch(nums, median + 1, end, target);  
  10.     } else {  
  11.         BinarySearch(nums, start, median - 1, target);  
  12.     }  
  13.     return -1;  
  14. }  
Feel free to ask questions in the comments below.