BINARY SEARCH ALGORITHM (Java, C++) | Algorithms and Data S... http://www.algolist.

net/Algorithms/Binary_search

Algorithms and Data Structures

with implementations in Java and C++

Data structures
Need help with a programming assignment? Get affordable programming homework help.
Algorithms

C++
Binary search algorithm
Books
Generally, to find a value in unsorted array, we should look through elements of an array one by one, until
Forum
searched value is found. In case of searched value is absent from array, we go through all elements. In average,
Feedback complexity of such an algorithm is proportional to the length of the array.

Situation changes significantly, when array is sorted. If we know it, random access capability can be utilized
very efficiently to find searched value quick. Cost of searching algorithm reduces to binary logarithm of the
array length. For reference, log2(1 000 000) ≈ 20. It means, that in worst case, algorithm makes 20 steps to
Support us
find a value in sorted array of a million elements or to say, that it doesn't present it the array.

Algorithm
to write
more tutorials Algorithm is quite simple. It can be done either recursively or iteratively:

1. get the middle element;

2. if the middle element equals to the searched value, the algorithm stops;
3. otherwise, two cases are possible:
to create new searched value is less, than the middle element. In this case, go to the step 1 for the part of the array,
visualizers before middle element.
searched value is greater, than the middle element. In this case, go to the step 1 for the part of the
array, after middle element.

Now we should define, when iterations should stop. First case is when searched element is found. Second one is
to keep sharing
when subarray has no elements. In this case, we can conclude, that searched value doesn't present in the array.
free knowledge
for you Examples
Example 1. Find 6 in {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.

Step 1 (middle element is 19 > 6): -1 5 6 18 19 25 46 78 102 114

Step 2 (middle element is 5 < 6): -1 5 6 18 19 25 46 78 102 114

Step 3 (middle element is 6 == 6): -1 5 6 18 19 25 46 78 102 114

Example 2. Find 103 in {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.
every dollar helps
Step 1 (middle element is 19 < 103): -1 5 6 18 19 25 46 78 102 114

Step 2 (middle element is 78 < 103): -1 5 6 18 19 25 46 78 102 114

TOP3 Articles
Step 3 (middle element is 102 < 103): -1 5 6 18 19 25 46 78 102 114
Quicksort
Step 4 (middle element is 114 > 103): -1 5 6 18 19 25 46 78 102 114
Depth-first search
Step 5 (searched value is absent): -1 5 6 18 19 25 46 78 102 114
Binary search tree

Complexity analysis
Huge advantage of this algorithm is that it's complexity depends on the array size logarithmically in worst
case. In practice it means, that algorithm will do at most log2(n) iterations, which is a very small number even
for big arrays. It can be proved very easily. Indeed, on every step the size of the searched part is reduced by
half. Algorithm stops, when there are no elements to search in. Therefore, solving following inequality in
whole numbers:

1 of 3 3/16/2017 12:51 PM
BINARY SEARCH ALGORITHM (Java, C++) | Algorithms and Data S... http://www.algolist.net/Algorithms/Binary_search

n / 2iterations > 0

resulting in

iterations <= log2(n).

It means, that binary search algorithm time complexity is O(log2(n)).

Code snippets.
You can see recursive solution for Java and iterative for C++ below.

Java

/**
* searches for a value in sorted array
*
* @param array
* array to search in
* @param value
* searched value
* @param left
* index of left boundary
* @param right
* index of right boundary
* @return position of searched value, if it presents in the array or -1, if
* it is absent
*/
int binarySearch(int[] array, int value, int left, int right) {
if (left > right)
return -1;
int middle = (left + right) / 2;
if (array[middle] == value)
return middle;
else if (array[middle] > value)
return binarySearch(array, value, left, middle - 1);
else
return binarySearch(array, value, middle + 1, right);
}

C++

/*
* searches for a value in sorted array
* arr is an array to search in
* value is searched value
* left is an index of left boundary
* right is an index of right boundary
* returns position of searched value, if it presents in the array
* or -1, if it is absent
*/
int binarySearch(int arr[], int value, int left, int right) {
while (left <= right) {
int middle = (left + right) / 2;
if (arr[middle] == value)
return middle;
else if (arr[middle] > value)
right = middle - 1;
else
left = middle + 1;
}
return -1;
}

2 of 3 3/16/2017 12:51 PM
BINARY SEARCH ALGORITHM (Java, C++) | Algorithms and Data S... http://www.algolist.net/Algorithms/Binary_search

Visualizers
1. Binary Search in Java Applets Centre

Two responses to "Binary Search Tutorial"

1. Guest on Oct 20, 2009 said:

The last value is never readed. For example...

int[] a = { 0, 3, 1, 7, 2, 8, 12, 53, 64, 95, 6, 71, 84, 9 };

and i want to search number 9

it returns that 9 is not in the array

Algorithm requires that source array is sorted in order to work correct.

2. Andres on Nov 5, 2008 said:

Hi, greetings from Argentina. I don't know whether this site is too old or very new. Anyway, I believe
there is a mistake with the binary search. I noticed that when "if (arr[middle] > value)" is true, it means
that you discard the first half of your array, considering 0,1,2,...,n. Then, in that case, the next sentence
should be left=middle + 1 instead of right=middle-1, which makes you consider only the first half of the
array. Best wishes, Andres from Buenos Aires, Argentina.

There is no mistake. If condition "value < arr[middle]" is true, it means, that value may
present only in the first part of an array. In this case second part of an array is discarded and
search continued in the first part. Thanks for your reply.

Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and
write new tutorials.

Every dollar helps!

Leave a reply

Your name (optional):

Your e-mail (optional):
Message:

3 of 3 3/16/2017 12:51 PM