二分查找（数据结构与算法java代码）_java算法题 二分查找

---

第一题 二分查找

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

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

---

第二题 搜索插入二分法（无重复元素）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

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

---

第三题 在排序数组中查找元素的第一个和最后一个

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

直接改代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        int i = 0, j = nums.length - 1;
        // 查找左边界
        while (i <= j) {
            int m = i + (j - i) / 2;
            if (nums[m] < target) {
                i = m + 1;
            } else if (nums[m] > target) {
                j = m - 1;
            } else {
                j = m - 1;
            }
        }
        if (i == nums.length || nums[i] != target) {
            result[0] = -1;
            result[1] = -1;
            return result;
        } else {
            result[0] = i;
        }
        // 查找右边界
        i = 0;
        j = nums.length - 1;
        while (i <= j) {
            int m = i + (j - i) / 2;
            if (nums[m] < target) {
                i = m + 1;
            } else if (nums[m] > target) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        // 当输入为[1] 1时， i == nums.length
        if (nums[j] != target) {
            result[0] = -1;
            result[1] = -1;
            return result;
        } else {
            result[1] = j;
        }
        return result;
    }
}

复用查找左边界

得先确认查找元素右边的离他最近的元素，无法确认时只能写target + 1，但这时又有两个问题，一是可能出现和target + 1重复的元素，导致无法通过nums[i] != target返回失败值-1，二是可能在返回-1时把-1的值改了

转化为查找元素

查找最左 -> target - 0.5，返回i

查找最右 -> target + 0.5，返回j

出现问题，得另外写代码确认所查找的元素是否存在，不然无法返回[-1, -1]

class Solution {
    public static int searchLeftRange(int[] nums, double target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = i + (j - i) / 2;
            if ((double)nums[m] < target) {
                i = m + 1;
            } else if ((double)nums[m] > target) {
                j = m - 1;
            } else {
                j = m - 1;
            }
        }
        if (i == nums.length) {
            return -1;
        } else {
            return i;
        }
    }
 
    public static int searchRightRange(int[] nums, double target) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = i + (j - i) / 2;
            if ((double)nums[m] < target) {
                i = m + 1;
            } else if ((double)nums[m] > target) {
                j = m - 1;
            } else {
                j = m - 1;
            }
        }
        if (i == nums.length) {
            return -1;
        } else {
            return j;
        }
    }
 
    public int[] searchRange(int[] nums, int target) {
        int[] result = {searchLeftRange(nums, (double)(target - 0.5)), searchRightRange(nums, (double)(target + 0.5))};
        return result;
    }
}

---

第四题 求平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5

自解

class Solution {
    public int mySqrt(int x) {
        // 1, 0平方根为自身
        if (x <= 1) {
            return x;
        }
        // 2以上的数
        int i = 0, j = x / 2;// 最大为原数一半
        while (i <= j) {
            int m = i + (j - i) / 2;
            if ((long) m * m < x) { // 不强转会出错
                i = m + 1;
            } else if ((long) m * m > x) {
                j = m - 1;
            } else {
                return m;
            }
        }
        return j;
    }
}

官解

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long) mid * mid <= x) { // 平方小于等于x的的最大整数ans
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

---

第五题 有效的完全平方根

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如  sqrt 。

class Solution {
    public boolean isPerfectSquare(int num) {
        if (num == 1) {
            return true;
        }
        // 特殊 ： 1
        int i = 0, j = num / 2;
        while (i <= j) {
            int m = i + (j - i) / 2;
            if ((long) m * m < num) {
                i = m + 1;
            } else if ((long) m * m > num) {
                j = m - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}