What is a binary search
Binary search is an efficient search algorithm
that finds the position of the target value in a sorted array
. Let's take a look at an example.
Example
Suppose you're searching a number 88
in a sorted array [5, 23, 56, 70, 88, 90]
. You could search linearly starting from the beginning of the array until you find the number or until you reach the end of the array.
The linear search can be implemented like this. The Search
method returns the index of the target value
if the target value exists, otherwise it returns -1
.
public int Search(int[] array, int target)
{
for (int i = 0; i < array.Length; i++)
{
if (array[i] == target)
{
return i;
}
}
return -1;
}
The algorithm works, but it ignores the fact that the array is sorted. Let's try to use it to our advantage.
The idea is to check the value in the middle of the array:
- if the middle value is
greater
than the target value, continue searching in theleft half
- if the middle value is
smaller
than the target value, continue searching in theright half
- if the middle value is
equal
to the target value, return theindex
of the middle value
The middle value of the array is 56
. 56
is less than 88
, which mean the target value could be in the right half. 88
cannot be in the left half because the array is sorted
-- all values to the left of 56
are smaller than 56
and therefore are also smaller less than 88
.
After the first step, we need to check only values from 70 to 90
. The next middle value is 88
, so we return index 4
.
Let's go through this process step by step again:
- Initial: array =
[5, 23, 56, 70, 88, 90]
, target =88
middle value
=56
,56
<88
, searching in the right half of the array[5, 23, 56, 70, 88, 90]
middle value
=88
,88
is equal to thetarget
value, hence return the index of the array4
Here's an iterative implementation of the binary search:
public int Search(int[] array, int target)
{
int low = 0;
int high = array.Length - 1;
while (low <= high)
{
int middle = low + (high - low) / 2;
if (array[middle] > target)
{
high = middle - 1;
}
else if (array[middle] < target)
{
low = middle + 1;
}
else
{
return middle;
}
}
return -1;
}