牛客網(wǎng)高頻算法題系列-BM17-二分查找-I
題目描述
請(qǐng)實(shí)現(xiàn)無重復(fù)數(shù)字的升序數(shù)組的二分查找
給定一個(gè) 元素升序的瘦棋、無重復(fù)數(shù)字的整型數(shù)組 nums 和一個(gè)目標(biāo)值 target ，寫一個(gè)函數(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};
// 測(cè)試用例，期望輸出： 6
System.out.println(search(nums, 13));
}
}
相信堅(jiān)持的力量丈攒！
