二分查找算法

• 题目： 二分查找

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

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

• 题目： 二维数组中的查找

public class BinarySearch2D {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int i = 0;
        int j = matrix[0].length - 1;
        while (j >= 0 && i < matrix.length) {
            if (target == matrix[i][j]) return true;
            else if (target > matrix[i][j]) i++;
            else j--;
        }
        return false;
    }
}

• 题目： 寻找峰值

public class Solution {
    public int findPeakElement(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int left = i == 0 ? Integer.MIN_VALUE : nums[i - 1];
            int right = i == nums.length - 1 ? Integer.MIN_VALUE : nums[i + 1];
            if (nums[i] > left && nums[i] > right) return i;
        }
        return -1;
    }
}

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

• 题目： 数组中的逆序对