leetcode-704.二分查找

题目

给定一个 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
提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

解题策略：

在leetcode大部分情况下，数据量都是庞大的，可能遇到算法的上界，也可能遇到算法的下界。而面对大量数据时，我采用的策略是牺牲部分空间，提高算法稳定性，将下界和上界维持在中间位置。

基础二分查找：

public static int search(int[] arr, target){int i = 0 , j = arr.length;while(i < j){int m = i + j >>> 1 //(计算机底层运算采用二进制，左移一位相当于除以2)if(target < arr[m]) j = m - 1;else if (arr[m] < target) i = m + 1;else retuen m;}return -1;
}

最好情况： O（1）

最坏情况： O（logn）

最好，最坏情况不稳定根本原因，if判断过程中，if执行次数 与 elseif执行次数 ，并且还需要进行target相同判断！因此出现了三次判断，而计算机的 0 和 1 更喜欢 true 和 false；

平衡二分查找

1、将判断条件缩减，即 if 和 else

2、if 和 else 判断意义修改，只进行范围寻找，寻找包含中间位置，不在加一，减一

3、判断意义修改，循环结束条件也得修改

4、如果找到target，不进行加一减一操作，导致死循环。设置 j - i > 1 ,作为出口

class Solution {public int search(int[] nums, int target) {int i = 0 , j = nums.length;while(1 < j-i){int m = (i+j) >>> 1;if(target < nums[m]){j = m;}else {i = m;}}if(target == nums[i]) return i;return -1;}
}