二分查找

题目描述

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1

思路

二分查找，用递归可以很容易实现。
用target和当前数组的中间元素比较，根据比较的结果向后递归即可。
需要注意两点：

• 递归终止条件：子数组只包含一个元素，则不需要继续向后递归
• 防止数组下标越界：
  • 如果递归左子数组，且mid为0时，不能继续递归，不然会越界
  • 因为数组可能包含重复元素，所以匹配到target后，还需要去求该元素第一次出现的下标。同样小心下标不要越界

代码

public int binarySearch(int[] nums, int target) {
        return myBinarySearch(nums, target, 0, nums.length-1);
    }
    
    /**
	 * @intention:二分查找也是递归的做法
	 */
	private int myBinarySearch(int[] nums, int target, int start, int end) {
		if(start == end && target != nums[start]) {
			return -1;		//找不到
		}
		int mid = start + (end-start)/2;	//mid偏左
		if(target < nums[mid]) {
			if(mid != 0) {
				return myBinarySearch(nums, target, start, mid-1);		//防止下标越界
			}else{
				return -1;
			}
		}else if (target > nums[mid]) {
			return myBinarySearch(nums, target, mid+1, end);
		}else {
			return findIndex(nums, target, mid);
		}
	}
	
	private int findIndex(int[] nums, int target, int tmpIndex) {
		while(target == nums[tmpIndex]) {
			if(tmpIndex == 0) {     //防止下标越界
				return tmpIndex;
			}
			tmpIndex--;
		}
		return tmpIndex+1;
	}

考察点

• 二分法