关于二分查找的知识（Leecode704二分查找）
关于二分查找的知识（Leecode704二分查找）在某种极端的情况下，算法二存在着数值溢出的风险。大家都知道，int的取值范围为2^32，因此当在极端情况下（high low）超过int的取值范围，由于java的特性，该值会变为负数。算法会因为数值溢出而产生错误结果。而使用第一种算法就完美地避开了这个问题。int middle = (high - low) / 2 low; //算法一 int middle = (high low) / 2; //算法二从数学角度来看，算法一的公式整理之后与第二种算法完全相同，并且，算法二看着也更为直观和简洁。但使用二分法都会采用第一种算法，为什么呢？public int search(int[] nums int target) { int low = 0 high = nums.length -1; while (low <= high)
Leecode每日一题/**
* 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
*
*
* 示例 1:
*
* 输入: nums = [-1 0 3 5 9 12] target = 9
* 输出: 4
* 解释: 9 出现在 nums 中并且下标为 4
*
*/
该题难度，官方定义简单。
题目简单易懂，一维数组求目标值下标，直接上代码
public static int search(int[] nums int target) {
for(int i = 0; i< nums.length; i ){
if(nums[i] == target) {
return i;
}
}
return -1;
}
直接一维数组循环，通过判断，返回下标。如果面试出此道题，真的是简单到了极致，当然，你要是提交这个答案，你的面试也就简单到了极致，可以回家休息啦。
很显然，该题为有序（升序）的整形数组，查找目标值下标，因此需要使用简单的算法：二分法。
public int search(int[] nums int target) {
int low = 0 high = nums.length -1;
while (low <= high) {
int middle = (high - low) / 2 low;
// int middle = (high low) / 2;
if (nums[middle] == target) {
return middle;
} else if (nums[middle] < target) {
low = middle 1;
} else {
high = middle - 1;
}
}
return -1;
}
如上就是一个简单的二分法示例，通过不断地取中，缩小查找范围，因为每次范围缩小一半，因此称为二分查找，大大的提高了算法效率。
注意：（二分法中间值的计算）
二分法中间值的算法，一共包含两种：
int middle = (high - low) / 2 low; //算法一
int middle = (high low) / 2; //算法二
从数学角度来看，算法一的公式整理之后与第二种算法完全相同，并且，算法二看着也更为直观和简洁。但使用二分法都会采用第一种算法，为什么呢？
在某种极端的情况下，算法二存在着数值溢出的风险。大家都知道，int的取值范围为2^32，因此当在极端情况下（high low）超过int的取值范围，由于java的特性，该值会变为负数。算法会因为数值溢出而产生错误结果。而使用第一种算法就完美地避开了这个问题。
官方题解：
二分查找
class Solution {
public int search(int[] nums int target) {
int low = 0 high = nums.length - 1;
while (low <= high) {
int mid = (high - low) / 2 low;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
high = mid - 1;
} else {
low = mid 1;
}
}
return -1;
}
}
复杂度分析
- 时间复杂度：O(logn)，其中 n是数组的长度。
- 空间复杂度：O(1)
