Currently working on mastering binary search and encountering difficulties while trying to use it to locate the "magic index" within an array, where the magic index is defined as A[i] == i.
While I have come across some Java implementations using recursion on this blog, I am exploring alternatives to recursion as it can be resource-intensive (and I want to test the suitability of binary search in this scenario).
Below is the code I have so far:
function magicIndex(arr) {
var result = arr, mid;
while (result.length > 1) {
mid = Math.floor(result.length / 2);
if (result[mid] === mid) {
return arr.indexOf(result[mid]);
} else if (mid > result[mid]) {
result = result.slice(mid+1, result.length);
} else {
result = result.slice(0, mid);
}
}
return arr.indexOf(result.pop());
}
The issue with the current algorithm is that it inconsistently slices the array during some test cases.
For instance, [-10, -3, 0, 2, 4, 8] yields 4, while [-10, 1, 0, 2, 5, 8] also produces 4.