【Leetcode完整解答筆記】704. Binary Search

題目提供一個由小到大的陣列 nums,以及一個目標數字 9。如果目標數字是陣列的其中一個元素,就回傳目標數字在陣列裡的位置,如果不在陣列裡頭,就回傳 -1。

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

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

Constraints:

  • 1 <= nums.length <= 104
  • -9999 <= nums[i], target <= 9999
  • All the integers in nums are unique.
  • nums is sorted in an ascending order.

這是很典型的 binary search 的題目。

這裡先定義陣列中即將判斷的範圍的最左邊的值為 left,最右邊的值為 right。

第一次先找出陣列中的中間的數字,如果中間的數字等於 target 就直接回傳。如果中間的數字大於 target 就把 right 改成 mid-1 (這樣就把範圍縮小了一半),如果中間的數字小於 target 就把 left 改成 mid+1。

這裡做個舉例會更容易理解,以 l 代表 left,r 代表 right。

nums:       [-1,0,3,5,9,12],target:9
              0 1 2 3 4 5
# 第一次判斷   l   m     r   target>nums[m] 因此 left=mid+1
# 第二次判斷         l m r   nums[m]=target 因此輸出 m

Python 解答:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right=0,len(nums)-1
        while(left<=right):
            mid=(left+right)//2;
            if(nums[mid]>target):
                right=mid-1
            elif(nums[mid]<target):
                left=mid+1
            else:
                return mid
        return -1

C 解答:

int search(int* nums, int numsSize, int target){
        int left=0;
        int right=numsSize-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]>target){
                right=mid-1;
            }
            else if(nums[mid]<target){
                left=mid+1;
            }
            else{
                return mid;
            }
        }
    return -1;
}

Leave a Comment

Your email address will not be published. Required fields are marked *