Search for a command to run...
Try your own input
Change the array and replay the algorithm from step one.
Current step
Duplicates break the usual trick: when arr[low], arr[mid] and arr[high] are all equal, neither side can be proven sorted. The only safe move is to shrink both ends by one, which is what costs this version its O(log n) guarantee.
Modified Binary Search
1function searchInARotatedSortedArrayII(arr, target) {2 let low = 0, high = arr.length - 1;//target: 3low: 0high: 93 4 while (low <= high) {5 const mid = Math.floor((low + high) / 2);6 7 if (arr[mid] === target) return true;8 9 // Ambiguous: neither side provably sorted10 if (arr[low] === arr[mid] && arr[mid] === arr[high]) {11 low = low + 1;12 high = high - 1;13 continue;14 }15 16 // Left half is sorted17 if (arr[low] <= arr[mid]) {18 if (arr[low] <= target && target <= arr[mid]) {19 high = mid - 1;20 } else {21 low = mid + 1;22 }23 }24 // Otherwise the right half is sorted25 else {26 if (arr[mid] <= target && target <= arr[high]) {27 low = mid + 1;28 } else {29 high = mid - 1;30 }31 }32 }33 return false;34}