今天开始学习数组，二分查找算法

1、实现动态的数组，可以进行简单的增删改查功能。

import java.util.Arrays;

/**
 * @Author: Onrion
 * @CreateTime: 2025/5/21
 * @Description:动态数组
 */
public class SimpleArrayList<T> {
    private int capacity = 10;

    private Object[] array;

    private int size;


    public SimpleArrayList() {
        array = new Object[capacity];
        size = 0;
    }

    private void add(T t) {
        if (size == capacity) {
            array = Arrays.copyOf(array, capacity * 2);
        }

        array[size] = t;
        size++;
    }

    private T get(int index) {
        if (index < 0 || index >= size) {
            return null;
        }
        return (T) array[index];
    }

    private T remove(int index) {
        if (index < 0 || index >= size) {
            return null;
        }

        // 0 1 2 3 4 5
        T t = (T) array[index];
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        size--;
        return t;
    }

    private void clear() {
        for (int i = 0; i < size; i++)
            array[i] = null;
        size = 0;
    }

    private int size() {
        return size;
    }

    private boolean isEmpty() {
        return size == 0;
    }

    /**
     * @param index
     * @param t
     * @return -1表示修改失败, 1代表修改成功
     */
    private int update(int index, T t) {
        if (index < 0 || index >= size) {
            return -1;
        }

        array[index] = t;
        return 1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(array[i]);
            if (i != size - 1) {
                sb.append(",");
            }
        }
        sb.append("]");

        return sb.toString();
    }
}

2、二分查找算法的实现，时间复杂度是O(log n);

    public static int binarySearch(int[] arr, int key) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2; // 不写(low+high)/2的原因是因为int类型可能出现溢出
            if (arr[mid] == key) {
                return mid;
            }
            if (arr[mid] < key) {
                low = mid + 1;
            } else if (arr[mid] > key) {
                high = mid - 1;
            }
        }
        return -1;
    }

3、做力扣69. x 的平方根

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

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

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

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

 题解代码：

    // 求算数平方数,舍去小数的部分
    // 如8需要返回2 9返回3 10返回3
    public int mySqrt(int x) {
        if (x == 0)
            return 0;
        int left = 1, right = x;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            long square = (long) mid * mid;
            if (square > x) {
                right = mid - 1;
            } else if (square < x) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return right; // 此时 right 是 floor(sqrt(x))
    }

4、做力扣33. 搜索旋转排序数组

题目描述：整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

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

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

题解代码：

    public static int newSearchInRotatedSortedArray(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            }

            // 判断哪一部分是有序的
            if (arr[mid] > arr[right]) { // 左半部分有序
                if (target >= arr[left] && target < arr[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // 右半部分有序
                if (target > arr[mid] && target <= arr[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }