# Binary search algorithm

By | March 25, 2017

## 1. Getting.

In binary search algorithm, we find an element x in a sorted array by using the principle of divide and conquer. First, we compare x to the middle point of the array. If x is less than the middle point, then we search the left of array. Otherwise, we look for the right half of the array. We repeat the process until we either find x or the sub-array has size 0. Figure 1: Time and Space complexity of Binary Search Algorithm.

## 2. Pseudocode.

Assume a sorted array a has N elements: a_left…a_right

Step 1: left = 1; right = N
Step 2: middle = (left + right)/2; //get the middle element
Compare a[middle] to x element, there are three cases happens:

• a[middle] = x: Found x element. Stop.
• a[middle] > x: // Continuously find x element in subarray a_left … a_middle-1.
right = middle – 1;
• a[middle] < x: // Continuously find x element in subarray a_middle+1 … a_right.
left = middle + 1;

Step 3: If lest <= right: Repeat Step 2 to find in remaining elements.
Otherwise. Stop // No more element for searching.

## 3. How it works.

Given a sorted array a has 8 elements: 1  2  4  5  6  8  12 15   and find x elements is 8. So the algorithm works as below:

• left = 1; right = 8; middle = (left + right)/2 = 4. So a[middle] = 5 • left = 5; right = 8; middle = 6; So a[middle] = 8; Found x = 8 and Stop here. ## 4. Implementation by Java.

### 4.1 Non recursive.

```/**
* Binary search algorithm non recursive implementation.
* @param a sorted array.
* @param x an element to be found.
* @return a position of the sorted array if found. Otherwise -1
*/
int binarySearch(int[] a, int x) {
int left = 0, right = a.length-1;
while(left <= right){
int middle = (left + right)/2;
if(a[middle] > x)
// Find in array index range from left to middle - 1
right = middle -1;
else if(a[middle] < x)
// Find in array index range from middle + 1 to right
left = middle + 1;
else return middle;// Found x
}
}
```

### 4.2 Recursive.

```      /**
* Binary search algorithm with recursive implementation.
* @param a sorted array.
* @param x an element to be found.
* @param left left-most of array.
* @param right right-most of array.
* @return a position of the sorted array if found. Otherwise -1
*/
int binarySearch(int[] a, int x, int left, int right) {
int middle = (left + right)/2;
if(a[middle] > x)
// Find in a subarray of the left of array.
return binarySearch(a, x, left, middle - 1);
else if(a[middle] < x)
// Find in a subarray of the right of array.
return binarySearch(a, x, middle + 1, right);
else return middle; //Found x
}
```

References:

• Robert Lafore, Recursion, in” Data Structures and Algorithms in Java “, Chapter 6.Second Edition, Sams Publishing , 2003.

This site uses Akismet to reduce spam. Learn how your comment data is processed.