[二分查找]

[Linjiayu6]

1 - 剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

# 双指针
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0: return 0
        result = 0
        i = 0
        while i < len(nums):
            if nums[i] < target: i += 1
            elif nums[i] == target: 
                i += 1
                result += 1
            else:
                break
        return result

# 二分查找
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        _len = len(nums)
        if _len == 0: return 0
        if _len == 1:
            return 1 if nums[0] == target else 0
        half = _len // 2

        left_nums = nums[0: half]
        right_nums = nums[half: ]
        return self.search(left_nums, target) + self.search(right_nums, target)

同类型34. 在排序数组中查找元素的第一个和最后一个位置

[Linjiayu6]

2 - 34. 在排序数组中查找元素的第一个和最后一个位置

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
nums = [5,7,7,8,8,10], target = 7
var searchRange = function(nums, target) {
    // 找个基准第一个值
    var start_i = nums.indexOf(target)
    if (start_i === -1) return [-1, -1]

    var nums = nums.slice(start_i + 1)
    var end_i = start_i
    while (nums && nums.length > 1) {
        var _m = Math.floor(nums.length / 2)
        var left = nums.slice(0, _m), right = nums.slice(_m)
        if (left[left.length - 1] === target) {
            // [8, 8] [9]
            if (right[0] !== target) return [start_i, end_i + left.length]
            // [8, 8] [8, 9]
            end_i += left.length
            nums = right
        } else {
            nums = left
        }
    }
    return [start_i, end_i]
};
console.log(searchRange(nums, target))