In this blog, we will
learn about the Binary search, it is the most popular search
algorithm and more efficient and also it is most commonly used technique for
search. Binary Search is also known as half-interval search,
logarithmic search, or binary chop.
The Binary
Search is an example of divide-and-conquer algorithm and it finds the position of a
target value or key within sorted array. In binary search algorithm it compares
the middle element of array to target value, if they are not equal, then half
of elements in array will be eliminated and it continuous search on remaining
half of array and again it will take
the middle element to compare to target value and repeating until the target
value is found.
Big O notation:
Binary Search
is faster than linear search, it don’t compare to each n element of arrays, so
in worst case, it makes O(logn) comparison
Here is a binary
search algorithm implementation in C#
static int BinarySearch(int[] arr, int low, int high, int key)
{
while(low <= high)
{
//Find middle position of array
int m = (low + high) / 2;
// Compare the middle element item to target value -key
if(key == arr[m])
{
return m;
}
else if (arr[m] > key)
{
high =
m-1;
}
else
{
low =
m+1;
}
}
return -1;
}
public static void Main()
{
#region binary search
int[] arr = new int[] { 5, 6, 7, 10, 23 , 50
};
foreach (var item in arr)
{
Console.Write(item.ToString() + ',');
}
Console.WriteLine();
int key = 23;
int index = BinarySearch(arr, 0,
arr.Length - 1, key);
Console.WriteLine($"Key : {key} Position : {index}");
#endregion
Console.Read();
}
Console Output:
No comments:
Post a Comment