?？途W(wǎng)高頻算法題系列-BM17-二分查找-I

題目描述

請實(shí)現(xiàn)無重復(fù)數(shù)字的升序數(shù)組的二分查找

給定一個 元素升序的、無重復(fù)數(shù)字的整型數(shù)組 nums 和一個目標(biāo)值 target ，寫一個函數(shù)搜索 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)（下標(biāo)從 0 開始），否則返回 -1

原題目見：BM17 二分查找-I

解法一：二分查找法

首先，考慮特殊情況，判斷如果數(shù)組為空，返回-1。

否則，使用low和high分別為數(shù)組的上下限，然后使用二分法判斷數(shù)組中的元素，判斷過程如下：

• 首先，循環(huán)終止的條件是low大于high
• 二分，mid取中間值
• 如果mid所在的值等于target，則返回mid
• 如果mid所在的值大于target，則更新high
• 如果mid所在的值小于target，則返回low

最后，如果二分查找沒找到等于target的值，返回-1。

代碼

public class Bm017 {
    /**
     * 二分查找-I
     *
     * @param nums   int整型一維數(shù)組
     * @param target int整型
     * @return int整型
     */
    public static int search(int[] nums, int target) {
        // 如果數(shù)組為空，返回-1
        if (nums == null || nums.length == 0) {
            return -1;
        }
        // low和high分別為數(shù)組的上下限
        int low = 0, high = nums.length - 1;
        // 循環(huán)終止的條件是low大于high
        while (low <= high) {
            // 二分，mid取中間值
            int mid = (low + high) / 2;
            // 如果mid所在的值等于target，則返回mid
            // 如果mid所在的值大于target，則更新high
            // 如果mid所在的值小于target，則返回low
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // 如果二分查找沒找到等于target的值，返回-1
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 4, 6, 10, 13, 14};
        // 測試用例，期望輸出： 6
        System.out.println(search(nums, 13));
    }
}

相信堅持的力量！