Chris's Lab

If you obey all the rules,you miss all the fun.

0%

[LeetCode] 704. Binary Search

發表於 分類於 ， ， Disqus：
這題用的技巧是二分搜尋法，原理是每次循環都會將搜索範圍縮小一半。

前言

　　這題用的技巧是二分搜尋法，原理是每次循環都會將搜索範圍縮小一半。演算法通常需要使用二分思想，即每次能夠排除一半的範圍，快速的找出陣列中所要求的元素位置，這樣時間複雜度可達 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.

範例

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
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

思路&筆記

這題用的技巧是二分搜尋法，原理是每次循環都會將搜索範圍縮小一半。

  1. middle = start + ( end - start ) / 2 可取得中間值
  2. 找出目標值在中間值的左側還是右側
  3. 搜索範圍越來越小，直到最後回傳中間值就是答案

[注意點] 之所以要用上述中間值的寫法會比較安全，因如果 start 和 end 趨近於最大數時，兩者相加起來的合可能會造成整數溢位

JAVA 實現

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 的寫法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

成績

Language Runtime Memory
Java 0ms 45.1MB
Python 251ms 17.9MB