Visualization
For example, let's search the number 7 in the following sorted int array.
left = 0; right = 12; middle = (0 + 12) / 2 = 6
1 2 5 7 9 12 15 18 20 23 25 28 30
The number we need to check is less than 15, so change upper bound right = middle - 1
left = 0; right = 5; middle = (0 + 5) / 2 = 2
1 2 5 7 9 12 15 18 20 23 25 28 30
The number we need to check is greater than 15, so change lower bound left = middle + 1
left = 3; right = 5; middle = (3 + 5) / 2 = 4
1 2 5 7 9 12 15 18 20 23 25 28 30
The number we need to check is less than 9, so change upper bound right = middle - 1
left = 3; right = 3; middle = (3 + 3) / 2 = 3
1 2 5 7 9 12 15 18 20 23 25 28 30
7 is the number we want to find, return its index 3.
Without Using Recursion:
public int binarySearch(int[] arr, int needle)
{
int left =0;
int right = arr.length - 1;
while(left <= right)
{
int middle = (left + right) / 2;
if(arr[middle] == needle)
{
return middle;
}
else if(arr[middle] < needle)
{
left = middle +1;
}
else
{
right = middle - 1;
}
}
return -1;
}
Using Recursion (without Helper Method):
public int binarySearch(int[] arr, int left, int right, int needle)
{
if(right < left)
{
return -1;
}
int middle = (left + right) / 2;
if(arr[middle] == needle)
{
return middle;
}
else if(arr[middle] < needle)
{
return binarySearch(arr, middle + 1, right, needle);
}
else
{
return binarySearch(arr, left, middle - 1, needle);
}
}
Using Recursion (with Helper Method):
public int binarySearch(int[] arr, int needle)
{
return binarySearchHelper(arr, 0, arr.length-1, needle);
}
public int binarySearchHelper(int[] arr, int left, int right, int needle)
{
if(right < left)
{
return -1;
}
int middle = (left + right) / 2;
if(arr[middle] == needle)
{
return middle;
}
else if(arr[middle] < needle)
{
return binarySearchHelper(arr, middle + 1, right, needle);
}
else
{
return binarySearchHelper(arr, left, middle - 1, needle);
}
}