二分查找算法利用数组的二段性，也就是数组可以被根据一定的规律分为两段，这两段具有不同的性质。
时间复杂度：
1次循环 ---> 剩 n/2
2次循环 ---> 剩 n/4
3次循环 ---> 剩 n/8
......
m次循环 ---> 剩 1
1 = n/n = n/(2的m次方)
m = logn
1. 基础二分查找
class Solution {
public int search(int[] nums, int target) {
int head = 0, tail = nums.length - 1;
while (head <= tail) {
int mid = head + (tail - head) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
tail = mid - 1;
} else {
head = mid + 1;
}
}
return -1;
}
}2. 二分查找左端点
当 nums[mid] < target，此时 mid 落在的地方一定不是我们想要的。左端点一定在 (mid, tail) 中。
当 nums[mid] >= target，有可能此时 mid 已经踩在了左端点，也有可能左端点尚在 mid 的左边。左端点一定在 (head, mid] 中。
查找左端点时计算 mid 必须取左，因为 tail 每次会踩到 mid 上，如果 mid 取右，当 mid 与 tail 重合时会死循环。
public int searchLeft(int[] nums, int target) {
int head = 0, tail = nums.length - 1;
while (head < tail) {
int mid = head + (tail - head) / 2;
if (nums[mid] < target) {
head = mid + 1;
} else {
tail = mid;
}
}
if (nums[head] == target && nums[tail] == target)
return head;
return -1;
}
二段性：前一段中的元素均小于 target，后一段的元素均大于等于 target。
找大于等于 target 的左端点。
二段性：由于题目只需要返回一个结果，任取一座山分析即可。每座山都能被分为上升区间和下降区间。
找递减区间的左端点。判断条件应使用 nums[mid] 和 nums[mid + 1] 进行比较，因为查找左端点时 mid 要取左，比较时应取 mid 右面的元素。
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
二段性：前一段中的元素均大于数组中的末位数，后一段中的元素均小于等于数组中的末位数。
找小于等于数组末位数的左端点。
二段性：前一段元素 val = index，后一段元素 val = index + 1。
找元素 val = index + 1 区间的左端点。
3. 二分查找右端点
当 nums[mid] > target，此时 mid 落在的地方一定不是我们想要的。右端点一定在 (head, mid) 中。
当 nums[mid] <= target，有可能此时 mid 已经踩在了右端点，也有可能右端点尚在 mid 的右边。右端点一定在 [mid, tail) 中。
查找右端点时计算 mid 必须取右，因为 head 每次会踩到 mid 上，如果 mid 取左，当 mid 与 head 重合时会死循环。
public int searchRight(int[] nums, int target) {
int head = 0, tail = nums.length - 1;
while (head < tail) {
int mid = head + (tail - head + 1) / 2;
if (nums[mid] > target) {
tail = mid - 1;
} else {
head = mid;
}
}
if (nums[head] == target && nums[tail] == target)
return head;
return -1;
}
二段性：前一段区间中元素的平方均小于等于 x，后一段区间中元素的平方均大于 x。
找元素平方小于等于 x 的右端点。
注意：指针即是 val，不需要创建数组。数据需要用 long 接收。