educative.io

Educative

Feedback for finding low index

let findLowIndex = function(arr, key) {
  let low = 0;
  let high = arr.length - 1;
  
  while (low <= high) {

    let mid = low + Math.floor((high - low) / 2);
    
    if (mid[arr] < key) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }

  }
  
  if (low < arr.length && arr[low] === key) {
    return low;
  }

  return -1;
};
let arr = [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6]
findLowIndex(arr, 2); //should return 3

Is it okay to use let with mid in while loop? I have modified the above solution from the given answer.

let findLowIndex = function(arr, key) {
  let low = 0;
  let high = arr.length - 1;
  let mid = Math.floor(high / 2);
  
  while (low <= high) {

    let midElem = arr[mid];
    
    if (midElem < key) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }

    mid = low + Math.floor((high - low) / 2);
  }
  
  if (low < arr.length && arr[low] === key) {
    return low;
  }

  return -1;
};
let arr = [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 6, 6]
findLowIndex(arr, 2); //should return 3

Which one is better?

Type your question above this line.

Course: https://www.educative.io/collection/5642554087309312/5679846214598656
Lesson: https://www.educative.io/collection/page/5642554087309312/5679846214598656/130003

Hi @Mohammad_Umar. Obviously, the variable mid should be declared only once as declaring it in a while loop will allocate the memory again and again. I encourage your effort, but you are also doing the same thing by declaring the midElem variable in the while loop. We should declare the mid variable outside the loop, and in the comparison, we should use array[mid] instead of making midElem again and again.

Here is the solution:

let findLowIndex = function(arr, key) {
  let low = 0;
  let high = arr.length - 1;
  let mid = Math.floor(high / 2);
  
  while (low <= high) {
    
    if (arr[mid] < key) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }

    mid = low + Math.floor((high - low) / 2);
  }
  
  if (low < arr.length && arr[low] === key) {
    return low;
  }

  return -1;
};

Happy Learning :smiley:

Thank you @Abdullah_Arshad

Can I add this condition also

if (high === -1){
    return high
 }

In case of a negative number, it will work. I can see this conditon in findHighIndex answer, but it will work here also.