[l, mid] [mid + 1, r]
static void Main(string[] args)
{
int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7 };
int target = 4;
int left = 0;
int right = nums.Length - 1;
while (left < right)
{
// 为什么不加1
// 当left + 1 = right, mid = left
// 如果nums[mid] < target, left会被加1
// 如果num[mid] >= target, right = mid = left, 跳出当前循环, 不会出现死循环的情况
int mid = (left + right) / 2;
if (nums[mid] < target)
{
// nums[mid] < target, 说明索引小于等于mid的值都不符合要求, target在mid + 1后面的位置
left = mid + 1;
}
else
{
// num[mid] >= target, 因为等于的存在, nums[mid]有可能就是结果, right要包含mid
right = mid;
}
}
// 结束循环的时候left == right
Console.WriteLine(left); // left = 3, 即nums[3] = 4;
}
[l, mid - 1] [mid, r]
static void Main(string[] args)
{
int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7 };
int target = 4;
int left = 0;
int right = nums.Length - 1;
while (left < right)
{
// 为什么加1
// 如果left + 1 = right, mid就等于left
// 如果nums[mid] <= target, left还会赋值成mid, 这样就进入了死循环
// 如果nums[mid] > target, right = mid - 1 = left, 跳出循环
int mid = (left + right + 1) / 2;
if (nums[mid] > target)
{
// nums[mid] > target, 说明索引大于等于mid的值都不符合要求, target在mid - 1前面的位置
right = mid - 1;
}
else
{
// nums[mid] <= target, nums[mid]有可能就是结果, left要包含mid
left = mid;
}
}
Console.WriteLine(left); // 3
}
如果找不到target
int[] nums = new int[] { 1, 2, 3, 5, 6, 7 };
int target = 4;
// [l, mid] [mid + 1, r] // 大于等于target的第一个数, 结果为3(索引)
// [l, mid - 1] [mid, r] //小于等于target的第一个数, 结果为2(索引)
练习题
LeetCode 35. 搜索插入位置
LeetCode 852. 山脉数组的峰顶索引
LeetCode 540. 有序数组中的单一元素
LeetCode 528. 按权重随机选择
LeetCode 374. 猜数字大小
LeetCode 275. H指数 II
LeetCode 81. 搜索旋转排序数组 II
LeetCode 4. 寻找两个正序数组的中位数(bushi)