public class Solution {
public int searchInsert(int[] nums, int target) {
int lo = 0;
int hi = nums.length1;
while (lo < hi) {
int mid = (lo + hi)/2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
hi = mid;
} else {
lo = mid+1;
}
}
return nums[lo] < target ? lo+1 : lo;
}
}
M
mostafa3
@mostafa3
6
Reputation
5
Posts
104
Profile views
0
Followers
0
Following
Posts made by mostafa3

Java solution using binary search

RE: C++ Solution (8 Lines)
I like your solution, but what if the array has only 2 values like [2, 1]. In that case i = high/2 = 0, and so nums[i1] = nums[1]. My C++ is rusty, but I think nums[1] will contain a garbage value and the outcome of your code will be unpredictable.

Commented Java binary search solution
public class Solution { public int findMin(int[] nums) { int lo = 0; int hi = nums.length1; if (nums[lo] < nums[hi]) { // no rotation return nums[lo]; } while (lo < hi) { int mid = (lo + hi)/2; if (nums[lo] <= nums[mid]) { // first half is sorted if (nums[mid+1] <= nums[hi]) { // second half is sorted return nums[mid+1]; // smallest element in second half } else { // second half is not sorted, so we search for our answer in the second half lo = mid+1; } } else { // first half isn't sorted, so we repeat our search on the first half hi = mid; } } return nums[lo]; } }