二分法 查找

2020-06-18 18:20 更新

題目

給定一個(gè) n 個(gè)元素有序的(升序)整型數(shù)組 nums 和一個(gè)目標(biāo)值 target ,寫(xiě)一個(gè)函數(shù)搜索 nums 中的 target,如果目標(biāo)值存在返回下標(biāo),否則返回 -1。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9 輸出: 4 解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4

示例 2:

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

提示:

你可以假設(shè) nums 中的所有元素是不重復(fù)的。 n 將在 [1, 10000]之間。 nums 的每個(gè)元素都將在 [-9999, 9999]之間。

經(jīng)典解法

1.引入開(kāi)頭start=0,end=nums.length-1

2.因?yàn)槭巧?,所以如果中間的值也就是 half=start+(end-start)/2;nums[half]大于target的話說(shuō)明target在half的后面,所以讓start=half+1從后半段中尋找

同理,小于的時(shí)候從end=half-1前半段查找

3.直到找到返回下標(biāo),如果沒(méi)有找到就會(huì)產(chǎn)生start>end,跳出while

class Solution {
    public int search(int[] nums, int target) {
        int start=0,end=nums.length-1;
        int half=0;  
        while(start<=end){
            half=start+(end-start)/2;
        if(nums[half]==target) return half;
        else if(nums[half]<target) start =half +1;
        else if(nums[half]>target) end =half -1;
       }
       return -1;   
    }

  
}

解法二:Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot = left + (right - left) // 2
            if nums[pivot] == target:
                return pivot
            if target < nums[pivot]:
                right = pivot - 1
            else:
                left = pivot + 1
        return -1

以上內(nèi)容是否對(duì)您有幫助:
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號(hào)
微信公眾號(hào)

編程獅公眾號(hào)