Binary Search

Binary Search

1. Implementation

(1) Search the index of target in the given set

public int binarySearch(int[] nums, int target) {
        int start = 0, end = nums.length - 1, mid;

        while (start <= end) {
            mid = start + (end - start) / 2; // avoid overflow

            if (nums[mid] == target) {
               return mid;
            }
            else if (nums[mid] < target) {
                start = mid + 1;
            }
            else {
                end = mid - 1;
            }
        }
        return -1;
    }

(2) Search the index of first element which is equal to target /

Search the index of first element which is equal or greater than target

public int binarySearch(int[] nums, int target) {
        int start = 0, end = nums.length - 1, mid;

        while (start < end) {
            mid = start + (end - start) / 2;

            if (nums[mid] < target) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return start;
    }

(3) Search the index of last element which is equal to target

public int binarySearch(int[] nums, int target) {
        int start = 0, end = nums.length - 1, mid;

        while (start < end) {
            mid = start + (end - start) / 2;

            if (nums[mid] > target) {
                end = mid - 1;
            }
            else {
                start = mid;
            }
        }
        return end;
    }