| 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; | |
| } | |
| } | |