圖解演算法第一天 -- 二分查找-有解無憂

二分查找

給定一個 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

題解

雙指標：左指標指向陣列頭，右指標指向陣列尾，取左右指標的中間數mid作為判斷值與target進行比較，如果mid下標的值大于target，則右指標左移至mid-1處，如果 mid下標的值小于target，則左指標右移至mid + 1處，回圈退出條件為左指標大于右指標，

在這里插入圖片描述
Python：

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

C++：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() -1;
        while (left <= right )
        {
            int mid = (left + right)/2;
            if (nums[mid] < target)
            {
                left = mid + 1;
            }else if(nums[mid] > target)
            {
                right = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    };
};

Java：

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

運行結果：
在這里插入圖片描述

雙非本科土木工程專業，自學IT，成功轉行，立志于被割韭菜前實作財務自由，愛好演算法，想做一個讓每個人都能看懂的演算法圖解平臺，歡迎大家關注官方認證的新生代農民工，

本文由博客一文多發平臺 OpenWrite 發布！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296225.html

標籤：其他

上一篇：平衡樹不好打?試試Trie字典樹！

下一篇：一文看懂從并查集到圖的基本演算法