704.Binary Search === ###### tags: `Easy`,`Array`,`Binary Search` [704. Binary Search](https://leetcode.com/problems/binary-search/) ### 題目描述 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` <= 10^4^ * -10^4^ < `nums[i]`, `target` < 10^4^ * All the integers in `nums` are **unique**. * `nums` is sorted in ascending order. ### 解答 #### Javascript ```javascript= function search(nums, target) { let min = 0; let max = nums.length - 1; while (max >= min) { const mid = Math.floor((max + min) / 2); if (nums[mid] === target) return mid; if (nums[mid] > target) { max = mid - 1; } else { min = mid + 1; } } return -1; } ``` > [name=Marsgoat][time=Apr 1, 2023] #### Python ```python= class Solution: def search(self, nums: List[int], target: int) -> int: L, R = 0, len(nums) while L < R: M = (L + R) // 2 n = nums[M] if n == target: return M if n > target: R = M else: L = M + 1 return -1 ``` ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)