二分法查找有序数组

题目链接-来源：力扣（LeetCode）

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

你可以假设数组中无重复元素。

示例 1:

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

思路：

借鉴上一题的思路。我们要找到 target，其实就是要找到 target - 1 右侧的最大值所处的位置。若存在 target，则返回目标索引，否则，该索引也是我们所需的插入位置。
时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int searchInsert(int[] nums, int target) {
        int index = helper(nums, target - 1);
        return index;
    }
    private int helper(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            int valM = arr[mid];
            if (valM <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}