这算得上是简单的一种算法了, 对有序序列进行二分查找,重点是注意边界值。
写关于边界值的问题最好通过模拟, 比如: [1, 2], 两个元素, left = 0, right = 1, mid = (right + left) / 2 = 0
nums[mid] = 1 => search 3 => left = mid + 1 = 1 => left == right, nums[left] = 2 < 3, left = mid + 1, left位置也就是插入位置
做一个简单的模拟可以保证边界问题顺利解决。
二分查找法
class Solution { public int search(int[] nums, int target) { // 做预处理 if (target < nums[0] || target > nums[nums.length - 1]) { return -1; } // 二分法:[left,right] int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + ((right - left) >> 1); if (target < nums[mid]) { right = mid - 1; } else if (target > nums[mid]) { left = mid + 1; } else { return mid; } } return -1; } }
二分查找并插入
class Solution { public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + ((right - left) >> 1); if (target < nums[mid]) { right = mid - 1; } else if (target > nums[mid]) { left = mid + 1; } else { return mid; } } return left; //没有搜索到, 返回插入位置: 这个时候最好模拟, 比如 [3, 5], 查找 4, left == right, nums[left] = 5, right--, 退出, 插入left位置 } }