二分法查找

二分法查找 LeetCode704二分查找

一直以来，都以为二分法很简单，但昨天一写代码就出问题，感觉还是理解得不够透彻。

二分查找

难度:简单

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

提示：

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

二分法可以有两种写法，定义区间不同，写法不同。值得注意的是，此区间在循环过程中保持不变，即mid改变，但区间性质不变。

1. target位于左闭右闭 []区间内

   此时，low==high可以成立
   

   假设target 为2，则下一步，high = mid - 1（保持闭区间，且无需再次查找mid处）
   

   同理，low = mid + 1

   故用Java实现

   class Solution {
       public int search(int[] nums, int target) {
            int low = 0, high = nums.length - 1;
            while (low <= high){
                int mid = low + (high-low)/2;
                if( nums[mid] == target){
                    return mid;
                }
                else if( nums[mid] > target){
                    high = mid - 1;
                }
                else if (nums[mid] < target){
                    low = mid + 1;
                }
            }
            return -1;
       }
   

2. target位于左闭右开 []区间内

   此时，low==high无意义，因为high本身并不在区间内。
   

   假设target 为2，则下一步，high = mid （保持左闭右开区间，且无需再次查找mid处）
   

   但由于左侧为闭区间，则low = mid + 1

   故用Java实现

   class Solution {
       public int search(int[] nums, int target) {
            int low = 0, high = nums.length;
            while (low < high){
                int mid = low + (high-low)/2;
                if( nums[mid] == target){
                    return mid;
                }
                else if( nums[mid] > target){
                    high = mid;
                }
                else if (nums[mid] < target){
                    low = mid + 1;
                }
            }
            return -1;
       }
   }