二分查找

算法分析

• 将n个元素分成个数大致相同的两半，取a[n/2]与x作比较。
• 如果x=a[n/2]，则找到x，算法终止，如果x<a[n/2]，则只在数组a的左半部继续搜索x，如果x>a[n/2]，则只在数组a的右半部分继续搜索x

代码实现

public class Solution {

    public static void main(String[] args) {
        System.out.println(new Solution().search(new int[]{1, 2, 3, 4, 5}, 3));
    }

    public int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            }
            if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }

}

• binarySearch(int[] nums, T x, int n)：在有序数组nums[n]的中查找x，如果找到返回x的数组下标，如果未找到则返回-1