Binary search algorithm

In this post, I will give a brief summary of binary search algorithm, together with some programming problems on this topic.

Algorithm Introduction

• It is a simple recursive searching algorithm.
• Scope of application: in ordered arrays

The pseudo code¹ is as follows:

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched
   Set lowerBound = 1 
   Set upperBound = n 
   while x not found 
    if upperBound < lowerBound 
		EXIT: x does not exists. 
	set midPoint = lowerBound + ( upperBound - lowerBound ) / 2 
	 
	 if A[midPoint] < x 
		 set lowerBound = midPoint + 1 
	 if A[midPoint] > x 
		 set upperBound = midPoint - 1 
	 if A[midPoint] = x 
         EXIT: x found at location midPoint 
   end while

In plain words, it recursively check whether the mid point value is the target, if the target is bigger, check the left half; if the target is smaller, check the right half.

Complexity

• Space complexity Only constant number of variables are used, therefore the space complexity is \(O(1)\).
• Time complexity Because each time after search, half of the array would be 'discarded', therefore the overall complexity is \(O(\log n)\), where \(n\) is the length of the array.

Java Implementation example

// Java - Non-recursive version
class Solution{
	public int binarySearch(int[] nums, int target) {
		int n = nums.length;
		int left = 0, right = n - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2; // Prevent add overflow
			if (nums[mid] == target) return mid;
			if (nums[mid] < target) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return -1;
	}
}

// Java - Revursive version
class Solution{
	public int binarySearch(int[] nums, int start, int end, int target) {
		if (start > end)
			return -1;
	    int mid = start + (end - start)/2; // Prevent add overflow
	    if (arr[mid] > target)
	        return binarySearch(arr, start, mid - 1, target);
	    if (arr[mid] < target)
	        return binarySearch(arr, mid + 1, end, target);
	    return mid;
	}
}

Questions

1. Leetcode 704 - Binary search - Basic implementation for this algorithm.
2. Leetcode 278 - First bad Version - Variation on look-up standards.
3. Leetcode 34 - Find First and Last Position of element in Sorted array - Variation on look-up standards and re-use of code.
4. Leetcode 33 - Search in rotated sorted array- Variation on the structure of array.
5. Leetcode 74 - Search a 2D matrix - Variation on the structure of input array, need to reduce the dimension of input.
6. Leetcode 162 - Find peak element - Another realization of binary search algorithm.

---

1. The pseudo code is derived from tutorials point ↩︎