目录
题目概述(简单难度)
题目链接:
思路与代码
思路展现
没啥好说的,经典二分查找法
代码示例
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ public int search (int[] nums, int target) { if(nums == null) { return -1; } int i = 0; int j = nums.length - 1; while(i <= j) { int mid = (i + j) / 2; if(nums[mid] < target) { i = mid + 1; }else if(nums[mid] > target){ j = mid - 1; }else { return mid; } } return -1; } }
时间复杂度: O(logn), 每次区间收敛一半
空间复杂度: O(1). 常数个变量
注意事项
这道题目注意在while循环的时候一定要加等于号,如果不加的话会有如下测试用例跑不过去:
以下代码错误:
while(i < j)