二分法 查找

題目

給定一個 n 個元素有序的（升序）整型數(shù)組 nums 和一個目標(biāo)值 target ，寫一個函數(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 的每個元素都將在 [-9999, 9999]之間。

經(jīng)典解法

1.引入開頭start=0,end=nums.length-1

2.因為是升序，所以如果中間的值也就是 half=start+(end-start)/2;nums[half]大于target的話說明target在half的后面,所以讓start=half+1從后半段中尋找

同理，小于的時候從end=half-1前半段查找

3.直到找到返回下標(biāo)，如果沒有找到就會產(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