Skip to content

704. Binary Search

https://leetcode.com/problems/binary-search/

js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  return searchInRange(nums, 0, nums.length - 1, target)
}

function searchInRange(nums, start, end, target) {
  if (start === end) {
    return nums[start] === target ? start : -1
  }

  const mid = (start + end) / 2 >> 0
  if (nums[mid] === target) {
    return mid
  } else if (nums[mid] < target) {
    return searchInRange(nums, mid + 1, end, target)
  } else {
    return searchInRange(nums, start, mid, target)
  }
}
py
class Solution:

    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        return self.search_in_range(nums, 0, len(nums) - 1, target)

    def search_in_range(self, nums, start, end, target):
        if start == end:
            return start if nums[start] == target else -1

        mid = (start + end) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            return self.search_in_range(nums, mid + 1, end, target)
        else:
            return self.search_in_range(nums, start, mid, target)