算法学习day05数组part扩展-69、35、34

package LeetCode.arraypart01;
/**
 * 69. x 的平方根
 * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
 * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
 * 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
 * 示例：
 * 输入：x = 4
 * 输出：2
 * */

public class MySqrtX_69 {
    public static void main(String[] args) {
        int x = 9;
        int result = mySqrt(x);
        System.out.println(result);
    }
    public static int mySqrt(int x) {
        int left = 0, right = x, ans = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if ((long) mid * mid <= x) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

}

package LeetCode.arraypart01;
/**
 * 35. 搜索插入位置
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法。
 */
public class SearchInsert_35 {
    public static void main(String[] args) {
        int [] arr = {1,3,5,7,9,11};
        int target = 12;
        int result = search_insert(arr,target);
        System.out.println(result);
    }
    /**
     * 暴力方法：
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static int search_insert_violence(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) { // 一旦发现大于或者等于target的num[i]，那么i就是我们要的结果
                return i;
            }
        }
        // 目标值在数组所有元素之后的情况，// 如果target是最大的，或者 nums为空，则返回nums的长度
        return nums.length;
    }

    /**
     * 二分法：
     * 时间复杂度：O(log n)
     * 空间复杂度：O(1)
     * */
    public static int search_insert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return right+1;
    }
}

package LeetCode.arraypart01;
/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 * 你必须设计并实现时间复杂度为 O(log n)的算法解决此问题。
 * 示例：
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 */

/**
 * 1.直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见target 的下标，但这个方法的时间复杂度为
 *      O(n)，没有利用到数组升序排列的条件。
 * 2.由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程
 * 考虑 target 开始和结束位置，其实我们要找的就是数组中「第一个等于 target 的位置」（记为leftIdx）
 *      和「第一个大于target 的位置减一」（记为rightIdx）。
 *
 * 二分查找中，寻找leftIdx 即为在数组中寻找第一个大于等于target 的下标，
 * 寻找rightIdx 即为在数组中寻找第一个大于target 的下标，然后将下标减一。
 * 两者的判断条件不同，为了代码的复用，
 *      我们定义 binarySearch(nums, target, lower) 表示在nums 数组中二分查找target 的位置，如果lower 为true，
 *      则查找第一个大于等于target 的下标，否则查找第一个大于target 的下标。
 * 最后，因为
 * target 可能不存在数组中，因此我们需要重新校验我们得到的两个下标
 * leftIdx 和 rightIdx，看是否符合条件，如果符合条件就返回[leftIdx,rightIdx]，
 * 不符合就返回[−1,−1]。
 *
 * */

public class SearchRange_34 {
    public static void main(String[] args) {
        int[] arr = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] result = search_range(arr, target);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }
    }
    public static int[] search_range(int[] nums, int target) {
        int leftBorder = searchBorder(nums, target, true);
        int rightBorder = searchBorder(nums, target, false);
        return new int[]{leftBorder, rightBorder};
    }
    //传入true表示寻找左边界，传入false表示寻找右边界
    public static int searchBorder(int[] nums, int target, boolean flag){
        int left = 0;
        int right = nums.length - 1;
        int border = -1;
        while(left <= right){
            int mid = (right + left) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                //true 寻找左边界
                if(flag){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
                border = mid;
            }
        }
        return border;
    }
}