Binary search algorithm

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
		}
		return - 1; // Not found.
	}

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) {
		if(left > right) return -1; // Not found.
		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.