Search a rotated array

search-a-rotated-array.js

const findTurningPoint = function(arr){
	let start = 0;
	let end = arr.length -1;
	let mid = Math.floor((end-start)/2);

	// We will keep track of start and end indexes and calculate mid based on them. 
	// First we will check if the array actually has a turning point. If not we will return -1

	if(arr[start]<arr[mid] && arr[mid]<arr[end]){
	// In a normal sorted array of unique elements:
	// we would expect the start would be smaller than mid and mid be smaller then end
		return -1;
	}

	// Now we will start adjusting our start and end points and recalculate mid on the go
	// Or end condition is when our start hits mid or our mid hits end
	while (start<mid && mid < end){
		if(arr[start]> arr[mid]){
			// if our start item is larger than the mid
			// we know that our turning point is between them
			// so we pull the end index to where mid is
			// and recalculate mid
			end = mid
			mid = start + Math.floor((end-start)/2);
		}else if(arr[mid]>arr[end] ){
			// if our mid item is larger than the end
			// we know that our turning point is between them
			// so we pull the start index to where mid is
			// and recalculate mid
			start = mid;
			mid = start+ Math.floor((end-start)/2);
		}
	}
	// When this is over we would land on the turning point
	// Note that turning point could be vague
	// For this implementation our turning point lands on the maximum of the array
	// The implementation can also be tweaked to land on the minimum of the array.
	// To achieve that replace Math.floor with Math.ceil
	return mid;
}

const binarySearchIterative = function(inputArr, searchKey){
	
	if (inputArr.length == 0){
		return -1;
	}
  // console.log(`searchKey : ${searchKey} - inputArr ${inputArr}`)
	if (searchKey < inputArr[0] || searchKey > inputArr[inputArr.length-1]){
		return -1;
	}
	
	let start = 0;
	let end = inputArr.length -1;
	let mid = start + Math.floor((end-start)/2);

	while(start<= end){
		if(searchKey > inputArr[mid]){
      start = mid+1;
    }else if(searchKey < inputArr[mid]){
      end = mid-1;
    }else{
      //we found the match so we return it.
      return mid;
    }
    mid = start + Math.floor((end-start)/2);
	}
  return -1;
}

let binarySearchRotated = function(inputArr, searchKey){
	const turningPoint = findTurningPoint(inputArr, searchKey);

	if (turningPoint == -1){
		// In this case we have a sorted array of 1 piece
		return binarySearchIterative(inputArr, searchKey);
	}else{
		// Let's check if our key is within our boundaries
		let maxIndex = turningPoint;
		let minIndex = (turningPoint + 1) 
		if(searchKey > inputArr[maxIndex] || searchKey < inputArr[minIndex] ){
			return -1;
		}
		// searchFirstPart
    let firstPartArr = inputArr.slice(0, turningPoint+1);
    // console.log(firstPartArr);
		let firstPartSearch = binarySearchIterative(firstPartArr, searchKey);
    // console.log(firstPartSearch);
		if (firstPartSearch != -1){
			return firstPartSearch;
		}
		let secondPartSearch = binarySearchIterative(inputArr.slice(turningPoint+1, inputArr.length), searchKey);
		if(secondPartSearch !=-1){
			return secondPartSearch + turningPoint+1;
		}
		return -1;
	}

}
// Tests

let inputArr = [4,5,6,7,1,2,3]
let searchKey = 3;
let res = binarySearchRotated(inputArr, searchKey);
console.log(res);

inputArr = [4,5,6,7,0,1,2,3]
searchKey = 3;
res = binarySearchRotated(inputArr, searchKey);
console.log(res);

inputArr = [1,2,3,4,5,6,7,8]
searchKey = 3;
res = binarySearchRotated(inputArr, searchKey);
console.log(res);


inputArr = [9,1,2,3,4,5,6,7,8]
searchKey = 3;
res = binarySearchRotated(inputArr, searchKey);

console.log(res);

inputArr = [1,2,3,4,5,6,7,8,0]
searchKey = 3;
res = binarySearchRotated(inputArr, searchKey);

console.log(res);

inputArr = [1,2,3,4,5,6,7,8,0]
searchKey = 90;
res = binarySearchRotated(inputArr, searchKey);

console.log(res);