Divide and Conquer

This is a searching pattern that works best on pre-sorted data where you grab a midpoint value and would then determine whether the thing you’re looking for is of greater or lesser value. If you were dealing with a million numbers (or numerical IDs) then it could save you a lot of time.

For example: suppose you DO have a million IDs, each one including part of the date in the ID. You might then use “Divide and Conquer” as sort of a “dumb” version of Binary Search to get the party started.

On the flip side, Divide and Conquer seems almost “in premise” like something that could be used in place of Sliding Window, or perhaps together with it to save some processing time.

For the example below, we’re looking at finding location of a target item in an ordered array.

function find_location_of_target_in_array(array, target) {

  if (typeof array[0] === "number") {
    array.sort((a, b) => a - b)
  } else {
    console.log(array.sort())
  }
  
  let windowStart = 0,
    windowEnd = array.length - 1;

  while (windowStart <= windowEnd) {
    let midPoint = Math.floor((windowStart + windowEnd) / 2 ), 
      currentElement = array[midPoint];

      if (array[midPoint] < target) {
        windowStart = midPoint + 1;
      } else if (array[midPoint] > target) {
        windowEnd = midPoint - 1;
      } else {
        return midPoint;
      }
  }

  return "nope"
}

console.log(find_location_of_target_in_array([1,2,5,4,3,51,6,20,7], 7))
console.log(find_location_of_target_in_array([1,2,3,4,5,6,7,20], 70))
console.log(find_location_of_target_in_array(["a","j","k","b","c"], "c"))

Cast of Characters:
-Expensive Accountants
-Window Washers
-Wile E Coyote with a Three Pronged Pitchfork
-Math Teacher on the Floor

Glossary of Code Personified

Return to the Pattern Directory