Table of contents
 Given problem
 Solution of Binary Search
 When to use
 Source code
 Some variants of Binary Search
 Some examples that uses Binary Search
 Wrapping up
Given problem
Assuming that we encounter the problem such as:
Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return 1.
Example:
Input: nums = [1,0,3,5,9,12], target = 9
Output: 4
How can we solve this problem in the logarithmic time?
Sequential search
The brute force way to solve an above problem is that we will use the linear search.
public int search(int[] nums, int target) {
int len = nums.length;
for (int i = 0; i < len; ++i) {
if (nums[i] == target) {
return i;
}
}
return 1; // not found
}
In this way, we have the complexity:
 Time complexity: O(n)
 Space complexity: O(1)
Quick Sequential search
In the sequential search way, we can find that it has two branch conditions such as a condition in for loop, and a remained condition in if statement.
So, we can optimize these by only using one condition.
public int search(int[] nums, int target) {
int end = nums.length  1;
int last = nums[end];
nums[end] = target;
int index = 0;
while (nums[index] != target) {
++index;
}
nums[end] = last;
if (index < end) {
return index;
} else if (last == target) {
return end;
}
return 1;
}
Solution of Binary Search
To reduce the time complexity of linear search, we will base on the condition of this array is the sorted array. We will use Binary Search to deal with it.
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length  1;
while (left <= right) {
int mid = left + (right  left) / 2;
if (nums[mid] == target) {
return mid;
} else if (target < nums[mid]) {
right = mid  1;
} else {
left = mid + 1;
}
}
return 1;
}
In this way, we have the complexity:
 Time complexity: O(log(n))
 Space complexity: O(1)
Some steps to solve problems with Binary Search:

Preprocessing  Sort if collection is unsorted.

Binary Search  Using a loop or recursion to divide search space in half after each comparison.

Postprocessing  Determine viable candidates in the remaining space.
When to use

When we have to search an element in a collection.
If our collection is unordered, we can always sort it first before applying Binary Search.

When we are given a sorted Array or LinkedList or Matrix, and we are asked to find a certain element, the best algorithm we can use is the Binary Search.

Binary search is not about sorted array or recursion, which are all very superficial. The essence of binary search is to reduce time complexity by eliminating half of the candidates.

When we have some trends such as an increased part or an decreased part of an array.
Source code

Iterative version
public static int binarySearch(int[] arr, int k) { int left = 0; int right = arr.length  1; while (left <= right) { // int mid = left + (right  left) / 2; int mid = (left + right) >>> 1; if (arr[mid] == k) { return mid; } else if (k < arr[mid]) { right = mid  1; } else { left = mid + 1; } } return 1; }

Recursive version
public static int binarySearch(int[] arr, int k, int left, int right) { if (left > right) { return 1; } // int mid = left + (right  left) / 2; int mid = (left + right) >>> 1; if (arr[mid] == k) { return mid; } else if (k < arr[mid]) { return binarySearchRecursive(arr, k, left, mid  1); } else { return binarySearchRecursive(arr, k, mid + 1, right); } }

Stride version
Another way to implement binary search is to go through the array from left to right making jumps.
 The initial jump length is n/2.
 The jump length is halved on each round: first n/4, then n/8, then n/16, … until finally the length is 1
 On each round, we make jumps until we would end up outside the array or in an element whose value exceeds the target value.
 After the jumps, either the desired element has been found or we know that it does not appear in the array.
public static int binarySearch(int[] arr, int k) { int pos = 0; int sz = arr.length; for (int stride = sz / 2; stride >= 1; stride /= 2) { while (pos + stride < sz && a[pos + stride] <= k) { pos += stride; } } if (a[pos] == k) return pos; return 1; }
Note:

With
int mid = (right + left) / 2;
, if right and left variable is large, then the expression ofright + left
can be overflow.So, we can have some solutions for this problem:
 Use
int mid = left + ((right  left) / 2);
.  Use
int mid = (left + right) >>> 1;
. This way is only suitable for Java developer.  With C/C++ developer, we can use
mid = ((unsigned int)left + (unsigned int)right)) >> 1;
.
 Use
Some variants of Binary Search

Comparing elements directly with specific condition
In this way, we will use the common format of Binary Search with source code:
int binarySearch(int[] nums, int target){ if(nums == null  nums.length == 0) { return 1; } int left = 0; int right = nums.length  1; while(left <= right){ int mid = left + (right  left) / 2; if(nums[mid] == target) { return mid; } else if(nums[mid] < target) { left = mid + 1; } else { right = mid  1; } } // End Condition: left > right, exactly right + 1 == left // No more candidate return 1; }
Some features of this variant:
 Most basic and elementary form of Binary Search
 Search Condition can be determined without comparing to the element’s neighbors (or use specific elements around it)
 No postprocessing required because at each step, you are checking to see if the element has been found. If you reach the end, then you know the element is not found
Some points in source code to identify:
 Initial Condition:
left = 0, right = length1
 Termination:
left > right
 Searching Left:
right = mid1
 Searching Right:
left = mid+1

Comparing an element with the its immediate right neighbor’s index in the array
int binarySearch(int[] nums, int target){ if(nums == null  nums.length == 0) return 1; int left = 0, right = nums.length; while(left < right){ int mid = left + (right  left) / 2; if(nums[mid] == target){ return mid; } else if(nums[mid] < target) { left = mid + 1; } else { right = mid; } } // Postprocessing: // End Condition: left == right // 1 more candidate if(left != nums.length && nums[left] == target) return left; return 1; }
Some features of this variant:
 An advanced way to implement Binary Search.
 Search Condition needs to access element’s immediate right neighbor
 Use element’s right neighbor to determine if condition is met and decide whether to go left or right
 Gurantees Search Space is at least 2 in size at each step
 Postprocessing required. Loop/Recursion ends when you have 1 element left. Need to assess if the remaining element meets the condition.
Some points in source code to identify:
 Initial Condition:
left = 0, right = length
 Termination:
left == right
 Searching Left:
right = mid
 Searching Right:
left = mid+1

Comparing an element with its immediate left and right neighbor’s index in the array
int binarySearch(int[] nums, int target) { if (nums == null  nums.length == 0) return 1; int left = 0, right = nums.length  1; while (left + 1 < right){ // Prevent (left + right) overflow int mid = left + (right  left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid; } else { right = mid; } } // Postprocessing: // End Condition: left + 1 == right // 2 more candidates if(nums[left] == target) return left; if(nums[right] == target) return right; return 1; }
Some features of this variant:
 An alternative way to implement Binary Search
 Search Condition needs to access element’s immediate left and right neighbors
 Use element’s neighbors to determine if condition is met and decide whether to go left or right
 Gurantees Search Space is at least 3 in size at each step
 Postprocessing required. Loop/Recursion ends when you have 2 elements left. Need to assess if the remaining elements meet the condition.
Some points in source code to identify:
 Initial Condition:
left = 0, right = length1
 Termination:
left + 1 == right
 Searching Left:
right = mid
 Searching Right:
left = mid
Some examples that uses Binary Search

Am I A Fibonacci Number (Simple)

Codeforces:Primes on Interval (Medium)
Wrapping up

Understanding about what the problem is that we can apply Binary Search.

Use smoothly some variants of Binary Search.
Refer:
https://leetcode.com/explore/learn/card/binarysearch
Guide to competitive programming: Learning and improving algorithms through concepts