二分查找算法

二分查找(普通版)

/**
 * 题目描述——二分查找(普通版)
 * 
 * 给定一个排序的整数数组（升序）和一个要查找的整数target，
 * 用O(logn)的时间查找到target第一次出现的下标（从0开始），
 * 如果target不存在于数组中，返回 -1。
 *
 */
public class Solution {

public static void main(String[] args) {
int[] array = {1, 2, 3, 3, 4, 5, 10};
int x = 3;

        System.out.print("数组array中的元素：");
for(int a: array) {
            System.out.print(" " + a);
        }
        System.out.println();

        System.out.println(x + "在数组array中的位置：" + Solution.binarySearch(array, x));
    }

/**
 * 二分查找算法——普通版
 * 
 * @param nums：待查找数组
 * @param target：待查找元素
 * @return
 */
public static int binarySearch(int[] nums, int target) {

int low = 0;                // 低指针
int high = nums.length -1;  // 高指针

// 查找过程
while(low <= high) {
int mid = (low + high) / 2; // 中间值指针

if(nums[mid] > target) high = mid - 1;          // 查找值位于前半部分
else if(nums[mid] < target) low = mid + 1;      // 查找值位于后半部分
else return mid;                                // 查找值所在位置
        }

return -1;
    }

}

二分查找(优化版)

/**
 * 题目描述——二分查找(优化版)
 * 
 * 给定一个排序的整数数组（升序）和一个要查找的整数target，
 * 用O(logn)的时间查找到target第一次出现的下标（从0开始），
 * 如果target不存在于数组中，返回 -1。
 *
 */
public class Solution {

public static void main(String[] args) {
int[] array = {1, 2, 3, 3, 4, 5, 10};
int x = 3;

        System.out.print("数组array中的元素：");
for(int a: array) {
            System.out.print(" " + a);
        }
        System.out.println();

        System.out.println(x + "在数组array中的位置：" + Solution.binarySearch(array, x));
    }

/**
 * 二分查找算法——优化版
 * 
 * @param nums：待查找数组
 * @param target：待查找元素
 * @return
 */
public static int binarySearch(int[] nums, int target) {

// 输入参数检查
if (nums == null || nums.length == 0 || 
                target < nums[0] || target > nums[nums.length - 1])
return -1;

int left = 0;                   // 左指针
int right = nums.length - 1;    // 右指针

// 目标值的查找
while (left < right - 1) {
int mid = left + (right - left) / 2;    // 中间值

if (nums[mid] < target) left = mid + 1;         // 目标值在后半部分
else if (nums[mid] > target) right = mid - 1;   // 目标值在前半部分
else right = mid;                               // 中间值的重新赋值
        }

// 返回目标值的位置
if (nums[left] == target) return left;
else if (nums[right] == target) return right;
else return -1;
    }

}

把排序数组转换为高度最小的二叉搜索树

class TreeNode {
public int val;
public TreeNode left, right;

public TreeNode(int val) {
this.val = val;
this.left = this.right = null;
    }
}

/**
 * 题目描述——把排序数组转换为高度最小的二叉搜索树
 * 
 * 给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树。
 *
 */
public class Solution {

/**
 * 把排序数组转换为高度最小的二叉搜索树——二分查找算法思想应用
 * 
 * @param A:待转换数组
 * @return
 */
public TreeNode sortedArrayToBST(int[] A) {
// 输入检查
if(A == null || A.length == 0) return null;

// 将排序数组转换为二叉搜索树
        TreeNode root = sortedArrayToBST(A, 0, A.length - 1);

// 返回二叉搜索树根节点
return root;
    }

/**
 * 把排序数组转换为高度最小的二叉搜索树——二分查找算法思想应用
 * 
 * @param A:待转换数组
 * @param start:二分查找起点
 * @param end:二分查找终点
 * @return
 */
public TreeNode sortedArrayToBST(int[] A, int start, int end){
// 边界值检查
if(start > end) return null;

// 二分查找中点——一定要学习利用这种中间点的设计方式
int mid = start + (end - start) / 2;

// 创建根节点
        TreeNode root = new TreeNode(A[mid]);
// 创建左子树
        TreeNode left = sortedArrayToBST(A, start, mid - 1);
// 创建右子树
        TreeNode right = sortedArrayToBST(A, mid + 1, end);
// 根节点与左右子树关联
        root.left = left;
        root.right = right;

// 返回根节点
return root;
    }

}