leetcode刷題記錄之704

704、二分查找

  給定一個 n 個元素有序的（升序）整型數組 nums 和一個目标值 target ，寫一個函數搜尋 nums 中的 target，如果目标值存在傳回下标，否則傳回 -1。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下标為 4
           

示例 2：

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中是以傳回 -1
           

提示：

1. 你可以假設 nums 中的所有元素是不重複的。
2. n 将在 [1, 10000]之間。
3. nums 的每個元素都将在 [-9999, 9999]之間。

難度：簡單  題目位址：https://leetcode-cn.com/problems/binary-search/

1、C語言代碼:

int search(int* nums, int numsSize, int target){
    for(int i = 0;i < numsSize;i++){
        if(nums[i] == target)
            return i;
    }
    return -1;
}
           

解釋： 順序周遊查找。

知識點回顧： 無。

2、Java代碼:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0; 
        int right = nums.length - 1; 
        while(left <= right) {
            //可以防止left+right溢出（超出整數範圍）
            int mid = left + ((right - left)>>2); 
            if(nums[mid] == target)
                return mid; 
            else if (nums[mid] < target)
                left = mid + 1; 
            else if (nums[mid] > target)
                right = mid - 1; 
            }
        return -1;
    }
}
           

解釋： 二分查找法。

知識點回顧： 無。

3、Python代碼：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        i = bisect.bisect(nums, target)
        return i - 1 if nums[i - 1] == target else -1
           

解釋： 利用Python的子產品求解。

知識點回顧：

1、Python 有一個 bisect 子產品，用于維護有序清單。bisect 子產品實作了一個算法用于插入元素到有序清單。在一些情況下，這比反複排序清單或構造一個大的清單再排序的效率更高。Bisect 是二分法的意思，這裡使用二分法來排序，它會将一個元素插入到一個有序清單的合适位置，這使得不需要每次調用 sort 的方式維護有序清單。

bisect.bisect_left(a,x, lo=0, hi=len(a))

查找在有序清單 a 中插入 x 的index。lo 和 hi 用于指定清單的區間，預設是使用整個清單。如果 x 已經存在，在其左邊插入。傳回值為 index。

bisect.bisect_right(a,x, lo=0, hi=len(a))

bisect.bisect(a, x,lo=0, hi=len(a))

這2個函數和 bisect_left 類似，但如果 x 已經存在，在其右邊插入。

bisect.insort_left(a,x, lo=0, hi=len(a))

在有序清單 a 中插入 x。和 a.insert(bisect.bisect_left(a,x, lo, hi), x) 的效果相同。

bisect.insort_right(a,x, lo=0, hi=len(a))

bisect.insort(a, x,lo=0, hi=len(a))

和 insort_left 類似，但如果 x 已經存在，在其右邊插入。

Bisect 子產品提供的函數可以分兩類： bisect* 隻用于查找 index， 不進行實際的插入；而 insort* 則用于實際插入。

4、JavaScript代碼：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    return nums.indexOf(target)
};
           

解釋： 直接利用函數。

知識點回顧：

1、indexOf() 方法可傳回某個指定的字元串值在字元串中首次出現的位置。

如果沒有找到比對的字元串則傳回 -1。

注意： indexOf() 方法區分大小寫。

文法：string.indexOf(searchvalue,start)

searchvalue：必需。規定需檢索的字元串值。

start：可選的整數參數。規定在字元串中開始檢索的位置。它的合法取值是 0 到 string Object.length - 1。如省略該參數，則将從字元串的首字元開始檢索。

傳回值：查找指定字元串第一次出現的位置，如果沒找到比對的字元串則傳回 -1。