[LeetCode 笔记] 704. Binary Search

前言

　　这题用的技巧是二分搜寻法，原理是每次循环都会将搜索範围缩小一半。演算法通常需要使用二分思想，即每次能够排除一半的範围，快速的找出阵列中所要求的元素位置，这样时间複杂度可达 O(log n)，这里有 JAVA 和 Python 的写法。

题目

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.

给定一个整数阵列 nums ，这是个上升排序阵列，和一个目标整数 target ，写一个方法去搜寻在 nums 阵列里的目标整数 target 。如果目标整数 target 存在就回传这个索引。否则回传 -1。
你必须写一个时间複杂度是 O(log n) 的演算法。

题目连结：https://leetcode.com/problems/binary-search/

题目限制

1 <= numRows <= 30
1 <= nums.length <= 104
104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

範例

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

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

思路&笔记

这题用的技巧是二分搜寻法，原理是每次循环都会将搜索範围缩小一半。

middle = start + ( end - start ) / 2 可取得中间值找出目标值在中间值的左侧还是右侧搜索範围越来越小，直到最后回传中间值就是答案

[注意点] 之所以要用上述中间值的写法会比较安全，因如果 start 和 end 趋近于最大数时，两者相加起来的合可能会造成整数溢位

JAVA 实现

class Solution {    public int search(int[] nums, int target) {        int start = 0; // 起点位置        int end = nums.length-1; // 终点位置                while (start <= end ){            int middle = start + (end-start)/2; // 中间值            if (target > nums[middle]){ // 目标值 > 阵列中间值                 start = middle + 1; // 重新定义起点，下次回圈从新的起点开始就好 (因为目标值一定比自己大，要不包含 middle 自己)            }else if (target < nums[middle]){ // 目标值 < 阵列中间值                 end = middle - 1; // 重新定义终点，下次回圈找到新的终点就好 (因为目标值一定比自己小，要不包含 middle 自己)            }else { // 目标值 = 阵列中间值                return middle; // 找到答案，回传中间值索引            }        }        return -1; // 没有这个数回传 -1    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。

class Solution:    def search(self, nums: List[int], target: int) -> int:        start = 0 # 起点        end = len(nums)-1 # 终点        while start <= end:            # 设定中间值            middle = start + (end-start)//2            # 判断 target 是否大于            if target > nums[middle]:                start = middle+1            # 判断 target 是否小于            elif target < nums[middle]:                end = middle-1            # 判断 target 是否等于 middle            else :                return middle        # 都没有        return -1

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/05/29/LeetCode-704-Binary-Search-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论