Data Structures
Overview
Number
String
Array
Stack
Hash
Tree
Trie
Probabilistic Data Structures
Big O

# Algorithm - Binary Search

Updated: 2021-12-15

The basic implementation:

public int binarySearch(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;

while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) {
return mid;
}

if (nums[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}

Find the largest value that is smaller or equal to the target

public static int binarySearch(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;

while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] == target) {
return nums[mid];
}

if (nums[high] < target) {
return nums[high];
}

if (low > 0 && nums[low] > target) {
return nums[low - 1];
}

if (nums[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}

The unsigned right shift operator >>> shifts a zero into the leftmost position, while the leftmost position after >> depends on sign extension.