Leetcode: Binary Search

By | 2018 年 9 月 21 日

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Note:

You may assume that all elements in nums are unique.
n will be in the range [1, 10000].
The value of each element in nums will be in the range [-9999, 9999].

Analyze

Simple question just has some conditions to consider carefully.

Use 2 indexes, start_index from 0, end_index from the arrays’ size – 1. Then each loop check the middle_index = (start_index + end_index) / 2. Check the number on middle_index with the target.

If it matches, then we found the target index in the array;

If nums[middle_index] is larger, then we should search in the range of start_index to middle_index - 1, because all the elements after middle_index will also be larger than target (nums is sorted);

Otherwise, search in the range of middle_index + 1 to end_index for next loop.

Notes

  • start_index == end_index condition
  • middle_index + 1 or middle_index - 1

Solution

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def search(nums, target)
    si = 0
    ei = nums.size - 1
    while si <= ei
        mi = (si + ei) / 2
        if nums[mi] == target
            return mi
        elsif nums[mi] < target
            si = mi + 1
        else
            ei = mi - 1
        end
    end
    return -1
end

发表评论

电子邮件地址不会被公开。 必填项已用*标注