278. First Bad Version

Problem Statement

First Bad Version - LeetCode

Pattern: Floor Ceil Similar to: Peak Index in a Mountain Array - LeetCode | Valid Mountain Array - LeetCode

---

Solution

public int firstBadVersion(int n) {
	int start = 0, end = n, mid ;
	while(start <= end) {
		mid = start + (end-start)/2;
		if(isBadVersion(mid)) // mid > key
			end = mid - 1;
		else                  // mid  < key
			start = mid + 1;
	}
	return start;
}

Notes

• A glorfied binary search ceil problem.

Peak Index in Mountain Array

public int peakIndexInMountainArray(int[] arr) {
	int start = 0, end =arr.length-1;
	while(start < end) {
		int mid = start + (end-start)/2;
		if(arr[mid + 1] > arr[mid]) start = mid + 1;
		else end = mid;
	}
	return start;
}

Notes

• Here we use the binary search ceiling approach
• this allows us to simplify the logic for (arr[mid+1] > arr[mid]) we can use this, since we dont have to worry about start or end ever being out of bounds, since the loop will break when start == end
  • Firstly start + (end - start) / 2 will always result in start <= mid < end. i.e. mid will never be equal to end since the division operation always returns the floor of the result. so when it comes down to 2 adjacent numbers start and end, mid will always point to start
  • secondly instead of returning when the element is found we keep it in range by adjusting end to end = mid and not end = mid - 1 which is typically the case.
  • if the key value is reached, then end will be reassigned to it.
  • at the end start and end will converge onto a singular value so any which one may be returned
• We can do the same thing the other way around
  • return ceil of the division int mid = start + (end-start + 1)/2. at the end mid will always point to end
  • keep key in range by reassigning start = mid
  • at the end start and end will converge onto a singular value so any which one may be returned

public int peakIndexInMountainArray(int[] arr) {
	int start = 0, end =arr.length-1;
	while(start < end) {
		int mid = start + (end-start + 1)/2;
		if(arr[mid - 1] > arr[mid]) end = mid- 1;
		else start = mid;
	}
	return start;
}