基础版：

/*** 使用二分查找算法在一个有序数组中查找目标值的位置。* 如果找到目标值，则返回其索引；如果没有找到，则返回-1。** @param a 一个已经按升序排序的整型数组* @param target 需要在数组中查找的目标值* @return 如果找到目标值，则返回其在数组中的索引；否则返回-1*/
public static int binarySearchBalance(int[] a, int target) {// 初始化两个指针 i 和 j，分别指向数组的起始位置和结束位置int i = 0; int j = a.length - 1;// 当 i 和 j 之间的距离大于1时继续循环// 注意：原条件 "1<j-i" 应该是 "1 < j - i" 的误写，正确的应该是 "i < j - 1"while (i < j - 1) { // 计算中间点 m，使用无符号右移操作符 >>> 1 来避免可能的溢出问题int m = (i + j) >>> 1; // 如果目标值小于中间点的值，则调整右边界 j 到 mif (target < a[m]) {j = m;} else {// 否则，调整左边界 i 到 mi = m;}}// 检查最终位置 i 处的元素是否等于目标值// 如果是，则返回其索引；如果不是，则返回-1表示未找到return (a[i] == target) ? i : -1;
}

插入值：

/*** 在指定范围内使用二分查找算法在一个有序数组中查找目标值的位置。* 如果找到目标值，则返回其索引；如果没有找到，则返回一个负数表示插入点。** @param a 一个已经按升序排序的长整型数组* @param fromIndex 查找范围的起始索引（包含）* @param toIndex 查找范围的结束索引（不包含）* @param key 需要在数组中查找的目标值* @return 如果找到目标值，则返回其在数组中的索引；*         如果未找到，则返回一个负数，表示目标值应插入的位置（-(插入点) - 1）*/
private static int binarySearch0(long[] a, int fromIndex, int toIndex, long key) {// 初始化两个指针 low 和 high，分别指向查找范围的起始和结束位置int low = fromIndex;int high = toIndex - 1;// 当 low 小于等于 high 时继续循环while (low <= high) {// 计算中间点 mid，使用无符号右移操作符 >>> 1 来避免可能的溢出问题int mid = (low + high) >>> 1;// 获取中间点位置的值long midVal = a[mid];// 如果中间点的值小于目标值，则调整左边界 low 到 mid + 1if (midVal < key) {low = mid + 1;}// 如果中间点的值大于目标值，则调整右边界 high 到 mid - 1else if (midVal > key) {high = mid - 1;}// 如果中间点的值等于目标值，则返回该中间点索引，表示找到了目标值else {return mid; // key found}}// 如果没有找到目标值，返回一个负数，表示目标值应插入的位置（-(插入点) - 1）return -(low + 1);  // key not found.
}

Leftmost 与 Rightmost：

如果我们希望返回最左侧元素，如对于数组 [1, 2, 3, 4, 4, 5, 6, 7]，查找元素4，结果是索引3

/*** 使用二分查找算法在一个有序数组中查找目标值的最左出现位置。* 如果找到目标值，则返回其最左索引；如果没有找到，则返回应插入的位置。** @param a 一个已经按升序排序的整型数组* @param target 需要在数组中查找的目标值* @return 如果找到目标值，则返回其在数组中最左边的索引；*         如果未找到，则返回目标值应插入的位置*/
public static int binarySearchLeftmost(int[] a, int target) {// 初始化两个指针 i 和 j，分别指向数组的起始位置和结束位置int i = 0, j = a.length - 1;// 当 i 小于等于 j 时继续循环while (i <= j) {// 计算中间点 m，使用无符号右移操作符 >>> 1 来避免可能的溢出问题int m = (i + j) >>> 1;// 如果目标值小于或等于中间点的值，则调整右边界 j 到 m - 1if (target <= a[m]) {j = m - 1;} // 否则，调整左边界 i 到 m + 1else {i = m + 1;}}// 返回 i，此时 i 是目标值应插入的位置或者目标值最左边出现的位置return i; 
}

查找最右侧的值

/*** 使用二分查找算法在一个有序数组中查找目标值的最右出现位置。* 如果找到目标值，则返回其最右索引；如果没有找到，则返回应插入的位置减一。** @param a 一个已经按升序排序的整型数组* @param target 需要在数组中查找的目标值* @return 如果找到目标值，则返回其在数组中最右边的索引；*         如果未找到，则返回目标值应插入的位置减一*/
public static int binarySearchRightmost(int[] a, int target) {// 初始化两个指针 i 和 j，分别指向数组的起始位置和结束位置int i = 0, j = a.length - 1;// 当 i 小于等于 j 时继续循环while (i <= j) {// 计算中间点 m，使用无符号右移操作符 >>> 1 来避免可能的溢出问题int m = (i + j) >>> 1;// 如果目标值小于中间点的值，则调整右边界 j 到 m - 1if (target < a[m]) {j = m - 1;} // 否则，调整左边界 i 到 m + 1else {i = m + 1;}}// 返回 i - 1，此时 i 是目标值应插入的位置，i - 1 是目标值最右边出现的位置return i - 1; 
}

二分查找-Leetcode 704

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

public static int binarySearchBalance(int[] a, int target) {int i = 0, j = a.length;while (1 < j - i) {int m = (i + j) >>> 1;if (target < a[m]) {j = m;} else {i = m;}}return (a[i] == target) ? i : -1;
}

搜索插入位置-Leetcode 35

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

public int searchInsert(int[] a, int target) {int i = 0, j = a.length - 1;while(i <= j) {int m = (i + j) >>> 1;if(target <= a[m]) {j = m - 1;} else {i = m + 1;} }return i;
}

搜索开始结束位置-Leetcode 34

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

 

public static int left(int[] a, int target) {int i = 0, j = a.length - 1;int candidate = -1;while (i <= j) {int m = (i + j) >>> 1;if (target < a[m]) {j = m - 1;} else if (a[m] < target) {i = m + 1;} else {candidate = m;j = m - 1;}}return candidate;
}public static int right(int[] a, int target) {int i = 0, j = a.length - 1;int candidate = -1;while (i <= j) {int m = (i + j) >>> 1;if (target < a[m]) {j = m - 1;} else if (a[m] < target) {i = m + 1;} else {candidate = m;i = m + 1;}}return candidate;
}public static int[] searchRange(int[] nums, int target) {int x = left(nums, target);if(x == -1) {return new int[] {-1, -1};} else {return new int[] {x, right(nums, target)};}
}