Binary search algo for leetcode heater question

Question

I was trying following leetcode heater problem (easy difficulty).

I wrote an algorithm which didn't work (I realised what I did wrong) so I went to see solution in discussion.

There I stumbled upon people using binary search but wasn't able to comprehend their logic. Can someone please explain me (algo) on how we can solve this using binary search (google search wasn't any help)

This was my non binary search algo which didn't work

/**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
var findRadius = function(houses, heaters) {
    let maximumDist = 1
  let currentDist = i = cHeaterIndex = 0
  while (i<houses.length){
    const cHeaterPosition = heaters[cHeaterIndex]
    if (houses[i] === cHeaterPosition || i === houses.length-1) {
      if (houses[i] === cHeaterPosition) {
        if (maximumDist < currentDist) {
          maximumDist = parseInt((currentDist - 1)/2)
        } 
      } else {
        maximumDist = currentDist - 1
      }
        currentDist = 1
        cHeaterIndex++
    }
    i++
    currentDist++
   }
   return maximumDist 
};

score 2 · Accepted Answer · 2020-09-26 05:51:46Z

2

Logic behind binary search is :

Find the left and right position of heater which best suits a particular house. Now, consider that if we are given sorted numbers and you have to find a value in that you will use binary search.

Same goes over here, you are given sorted numbers in terms of heater positions and search value is particular house position . Now, you have to find an index of heater position value which is nearest to this house position.

Example :

heaters[] = {1,2,3,8} house_position = 5.

So, closest value of heater from left is 3 (index = 2) which we can find by binary search . Now, this is left position of heater which can heat this house. Right positioned heater can also heat the house which is at next index(index=3) whose value is 8. So, this particular house can be heated by both heaters at position 3 and 8. Out of this we will find best heater position which has minimum distance from the house (since that will have minimum radius). In this case it is heater at position 3(index=2), whose distance from house is 2.

This is the logic of binary search for this question.

Here is the working example of the same (JAVA code).

 /**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
var findRadius = function(houses, heaters) {
    var totalhouses = houses.length, totalheaters = heaters.length, index=0, currindex=0, max = 0, currmin;
    heaters.sort((a, b) => a - b);
    while(index< totalhouses) {
        currindex = search(heaters, houses[index], 10);
        if(currindex==-1) {  //if left positioned heater is not present
            currmin = heaters[0] - houses[index];
        } else {
            if(currindex+1 < totalheaters) {
                currmin = Math.min(heaters[currindex+1] - houses[index], houses[index] - heaters[currindex]);
            } else {   //if right positioned heater is not present
                currmin = houses[index] - heaters[currindex];
            }
        }
        max = Math.max(max, currmin); 
        index++;
    }
    return max;
};

var search = function(heaters, value) {  //binary search to find best possible left positioned heater for the house
    var start=0,end = heaters.length-1, mid=0;
    while(start<=end) {
        mid = Math.floor((start + end) / 2);
        if(heaters[mid] == value){
            return mid;
        } else if(heaters[mid] > value) {
            end = mid-1;
        } else {
            start = mid+1;
        }
    }
    return end;
}

edited Sep 26, 2020 at 5:51

answered Sep 26, 2020 at 3:46

user11935734

Sign up to request clarification or add additional context in comments.

6 Comments

user11935734 Over a year ago

@Diza Moa If you have any issues related to solution or logic behind binary search you can ask the same. Thanks.

user11935734 Over a year ago

@downvoter may I know the reason of downvote.@Diza Mora was asking solution based on binary search and before giving the solution I have tried the same on leetcode as well and it is running fine.

user11935734 Over a year ago

The question was asking for algorithm not the exact code. The earlier code was added so as to make algorithm more clear. But I have edited the code and updated it to javascript. Thanks.

user11935734 Over a year ago

@Diza Moa We can optimise code further but for keeping the algorithm clear I have tried to make it more readable. If you have any issues related to this please let me know.

user11935734 Over a year ago

@Diza Moa If your issue is resolved can you please accept and upbote the answer.

|

Collectives™ on Stack Overflow

Binary search algo for leetcode heater question

1 Answer 1

Example :

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Example :

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related