Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

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
Copy the code

Example 2:

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

Note:

1 <= nums.length <= 10^4
-10^4 < nums[i], target < 10^4
All the integers in nums are unique.
nums is sorted in ascending order.
Copy the code

parsing

Given an integer array nums sorted in ascending order and an integer target, write a function to search for targets in NUMS. If the target exists, its index is returned. Otherwise -1 is returned. They specify that we have to write an algorithm with order log n runtime complexity.

Binary Search: Binary Search, Binary Search, Binary Search, Binary Search, Binary Search, Binary Search, Binary Search, Binary Search So the solution is pretty clear, which is to use binary search. The idea is simple:

  • We initialize two Pointers I and j to the head and tail of nums
  • Mid = (I + j) // 2; mid = (I + j) // 2; If nums[mid] is greater than target, then target may be in the first half. If nums[mid] is less than target, target may be in the second half.
  • If I >j, I can’t find it, so just return -1

The time complexity is O(log n) and the space complexity is O(1).

answer

class Solution(object):
    def search(self, nums, target):
        i = 0
        j = len(nums) - 1
        while i <= j:
            mid = (i + j) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                j = mid - 1
            else:
                i = mid + 1
        return -1	
Copy the code

The results

Given in the Python online submissions for Binary Search. Memory Usage: 10000 ms Given in the Python online submissions for Binary Search.Copy the code

The original link

Leetcode.com/problems/bi…

Your support is my biggest motivation