import java.util.*;

/**
 * Fancy Binary Search
 * fancy-binsearch
 * 
 * 
 * Input:
 *     arr: A sorted list of ints
 *     x: A value to find
 * 
 * Output:
 *     The lowest index i such that arr[i] == x, or -1 if x not in arr
 * 
 * Example:
 *     >>> find_first_in_sorted([3, 4, 5, 5, 5, 5, 6], 5)
 *     2
 *
 * @author derricklin
 */
public class FIND_FIRST_IN_SORTED {

    public static int find_first_in_sorted(int[] arr, int x) {
        int lo = 0;
        int hi = arr.length;

        while (lo < hi) {
            int mid = (lo + hi) / 2; // check if this is floor division

            if (x == arr[mid] && (mid == 0 || x != arr[mid-1])) {
                return mid;
            } else if (x <= arr[mid]) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        return -1;
    }

}