Binary Search, a searching algorithm…

A topical dive into this searching algorithm. A binary search, as a searching algorithm, must be done on a sorted array, with the desired target, in mind. The target, (aka whatever is this middle point) in the array is reached by assessing the left and right perspectives in the array. Binary search can be coded aka done aka executed iteratively and recursively.

ANALOGY FOR BINARY SEARCH IS DIVIDE AND CONQUER

In this Leetcode problem, Binary Search #704, we are checking to see the target, actually exists. Let’s break down the steps of consideration for this problem.

• We are given this num’s array is [-1, 0, 3, 5, 9, 12], and to check for a target of 9. The target 9 sits at the index of 4. Most importantly, the provided nums array are already sorted in ascending order — we need this to execute a binary search algorithm.

Input:   nums =   [-1, 0, 3, 5, 9, 12], target = 9 
Index placement is[ 0, 1, 2, 3, 4, 5 ]  

• If we cannot find this target, then we will need to return -1.
• HOWEVER, when and if we do find this target, we want to return its index, at the Output of 4 aka target 9.

1. Now must define variables of let low = 0 is our left pointer, defining our first index, while high = nums.length -1, is the right pointer at the end of the array aka our last index with the minus one at the end.
2. Starting our while loop’s argument with (low <= high) returns true which recognizes that low is indeed less than equal to high.
3. const mid variable will calculate the location of the index. Factor in for any potential occurring changes between the left and right pointers as we loop through the array towards our mid index.
4. Math.floor will assist in rounding down any decimal numbers into whole integers.
5. If conditional arguments (nums[mid] < target) and (nums[mid] > target), respectively allow us when needed to get to the mid to move the low (aka left) pointer in ascension, or move the high (aka right) pointer towards the left or low. Otherwise, should mid in nums[mid] is actually equal to our target (at the index perspective) then let's return mid.
6. Finally only return -1 when the target of 9 does not exist.

// iterative perspective to solve this problem!
// nums =   [-1, 0, 3, 5, 9, 12], target = 9
var search = function(nums, target) {

   
    let low = 0,
    high = nums.length - 1;

      while (low <= high) {
        const mid = Math.floor((low + high) / 2);
    
        if (nums[mid] < target) {
          low = mid + 1;       //continue increasing the left pointer to find the target
       
        } else if (nums[mid] > target) {
            high = mid - 1;  
        } else return mid;
     
      }
    return -1;    //did not target
};
////////////////////////// RECURSIVE APPROACH //////////////////
var search = function(nums, target) {
    
     return findTarget(nums, target, 0, nums.length - 1);
};
function findTarget(nums, target, low = 0, high = nums.length - 1) {
    if (low > high) {
        return - 1;
    }
    
    const mid = Math.floor((low + high) / 2) ;
    if (nums[mid] > target) {
        return findTarget(nums, target, 0, mid - 1);
    }  else if (nums[mid] < target) {
        return findTarget(nums, target, mid + 1, high);
    } else  
        return mid;

Resources I found helpful:

• Chimi and John. “Algorithms: What is Binary Search (JavaScript).”
• HackerRank. “Algorithms: Binary Search.”

Happy coding, Friends.