leetcode-704-Binary-Search

发表于   |  

描述

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:

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

Example 2:

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

Note:

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

分析

二分查找，唔。

解决方案1（Python）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = (high-low) // 2 + low
            now = nums[mid]
            if now == target:
                return mid
            elif now > target:
                high = mid - 1
            else:
                low = mid + 1
        return -1

解决方案2(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, h = nums.length - 1;
        while (l <= h) {
            int mid = (l + h) >>> 1;
            if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                h = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

解决方案3（Golang）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := (right-left) / 2 + left
        num := nums[mid]
        if num == target {
            return mid
        } else if num > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return -1
}

相关问题

题目来源