# 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
```