二分查找

在一次面试中，让手写二分查找代码，
我开始写了一个递归版,面试官让写了一个非递归版的,这个很快也写出来了,最后面试官有要求改进成求元素首次或者最后一次出现的位置,提示我稍微改动就可以实现,可惜当时没有写出来．

package com.cqs.leetcode.ds.search;

import com.cqs.leetcode.ds.ArraysUtils;
import com.cqs.leetcode.ds.sort.ISort;
import com.cqs.leetcode.ds.sort.MergeSort;

import java.util.Random;

/**
 * Author:li
 * <p>
 * create date: 18-5-30 09:27
 */
public class BinarySearch {


    /**
     * 查询target在有序数组sort中首次出现的位置 若不存在返回-1
     *
     * @param sort
     * @param target
     * @return
     */
    public int searchFirst(int[] sort, int target) {
        if (sort == null || sort.length == 0) return -1;
        int left = 0, right = sort.length - 1, mid = (left + right) / 2;
        do {
            if (target == sort[mid]) {
                //mid一定会大于等于left
                if (mid == left || sort[mid - 1] != target) return mid;
                right = mid - 1;
            } else if (target < sort[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = (left + right) / 2;
        } while (left <= right);
        return -1;
    }

    /**
     * 查询target在有序数组sort中最后一次出现的位置 若不存在返回-1
     *
     * @param sort
     * @param target
     * @return
     */
    public int searchLast(int[] sort, int target) {
        if (sort == null || sort.length == 0) return -1;
        int left = 0, right = sort.length - 1, mid = (left + right) / 2;
        do {
            if (target == sort[mid]) {
                //mid一定会小于等于right
                if (mid == right || sort[mid + 1] != target) return mid;
                left = mid + 1;
            } else if (target < sort[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = (left + right) / 2;
        } while (left <= right);
        return -1;
    }


    /**
     * 基于循环实现二分查找
     *
     * @param sort
     * @param target
     * @return
     */
    public int search0(int[] sort, int target) {
        if (sort == null || sort.length == 0) return -1;
        int left = 0, right = sort.length - 1, mid = (left + right) / 2;
        do {
            if (target == sort[mid]) {
                return mid;
            }
            if (target < sort[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            mid = (left + right) / 2;
        } while (left <= right);
        return -1;
    }

    /**
     * 递归实现二分查找
     *
     * @param sort
     * @param target
     * @return
     */
    public int search(int[] sort, int target) {
        if (sort == null || sort.length == 0) return -1;
        return search(sort, 0, sort.length - 1, target);
    }

    private int search(int[] sort, int left, int right, int target) {
        if (left > right) return -1;
        int mid = (left + right) / 2;
        if (target == sort[mid]) {
            return mid;
        }
        if (target < sort[mid]) {
            return search(sort, left, mid - 1, target);
        }
        return search(sort, mid + 1, right, target);
    }


    public static void main(String[] args) {
        BinarySearch bs = new BinarySearch();
        ISort sort = new MergeSort();
        int[] nums = ArraysUtils.randInts(30);
//        int[] nums = {0, 1, 2, 5, 5, 5, 6, 6, 7, 8};
        sort.sort(nums);
        //有序数组
        ArraysUtils.print(nums);
        int idx = new Random().nextInt(nums.length);
//        idx = 5;
        int target = nums[idx];
        System.out.println("target:" + nums[idx]);
        System.out.println("index: " + idx + "\t" + bs.search(nums, target) + "\t" + bs.search0(nums, target)
                + "\t首次位置:" + bs.searchFirst(nums, target) + "\t最后位置:" + bs.searchLast(nums, target));
    }
}

结果:

image.png