Binary Search Decoded: Navigating Search Algorithms
Tags: javascript, programming, beginners, webdev
Published: 2023-08-31 18:07:36


## What is Binary Search & how does it work ?  🤔

Binary Search is a searching algorithm that is applicable **only to sorted arrays**. It operates by repeatedly dividing the search interval in half, narrowing down the potential locations of the target value with each iteration. This cycle of dividing and searching continues until the target value has been found or until it is determined that the element is not in the array.

## What is the Space & Time Complexity of Binary Search? ⏰

The average time complexity of the Binary Search algorithm is O(log N), where N is the number of elements in the array. This logarithmic time complexity arises from the fact that with each step, the search interval is halved, leading to a rapid reduction in the number of remaining elements to search through.

The space complexity of Binary Search is O(1), indicating constant space usage. The algorithm doesn't require additional memory that scales with the size of the input; it only uses a few variables to keep track of the indices and midpoints during the search.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4a7vipg84vpfgaiu7mjm.gif)


## Exploring Binary Search: A Deep Dive with Code Examples 🧑🏻‍💻 ##

### Problem 1:

Given a sorted array and a target integer value, find and return the index location of the target value.

Example: 

array = [1,4,7,10,11,34,40,42]

target = 34

Technique & Approach being used: 

```jsx

function search(arr, target){
	// Initalize pointers

	// left: starts at the beginning of the array 
	let left = 0;  
	// right: starts at the end of the array
	let right = arr.length - 1; 

	//condition: continue loop until left pointer is <= to the right pointer
	while(left <= right){

		// calculate the midpoint of the current search interval
		let mid = Math.floor((left + right) / 2); 
		
		// if the mid point === the target value "we found the target's location"
		if(arr[mid] === target){
				//return the index value of the mid point
				return mid
		}
		// otherwise if the target value is less than the midpoint value. 
		else if (target < arr[mid]){
		//narrow the search range to the left half
		right = mid -1 
		}
		// otherwise if the target is larger than the midpoint value
		else{
		// narrow the search range to the right half
		left = mid + 1
		}
	}
	//if the loop completes without finding the target return -1. 
	return -1 
}

//Time complexity: O(logn)
//Space complexity: O(1)
```

### Problem 2:

There is an integer array `nums` sorted in ascending order (with **distinct** values).

Prior to being passed to your function, `nums` is **possibly rotated** at an unknown pivot index `k` (`1 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (**0-indexed**). For example, `[0,1,2,4,5,6,7]` might be rotated at pivot index `3` and become `[4,5,6,7,0,1,2]`.

Given the array `nums` **after** the possible rotation and an integer `target`, return *the index of* `target` *if it is in* `nums`*, or* `-1` *if it is not in* `nums`.

You must write an algorithm with `O(log n)` runtime complexity.

Example 1: 

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2: 

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

```jsx
function search(nums, target) {
	// Initalize pointers

	// left: starts at the beginning of the array 
    let left = 0;
	// right: starts at the end of the array 
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid; // Target found, return the index
        }

        if (nums[left] <= nums[mid]) {
            // If the left part is sorted
            if (nums[left] <= target && target < nums[mid]) {
                // If the target is within the range of the sorted left part
                right = mid - 1; // Adjust the right pointer
            } else {
                left = mid + 1; // Adjust the left pointer
            }
        } else {
            // If the right part is sorted
            if (nums[mid] < target && target <= nums[right]) {
                // If the target is within the range of the sorted right part
                left = mid + 1; // Adjust the left pointer (narrow to right half)
            } else {
                right = mid - 1; // Adjust the right pointer (narrow to left half)
            }
        }
    }

    return -1; // Target not found, return -1
}

// Time Complexity: O(log n)
// Space Complexity: O(1)
```
##A short summary by Fireship: ##
{% embed https://youtu.be/MFhxShGxHWc?si=rGgLvettlsbmZbQT %}

References: 

- https://www.geeksforgeeks.org/complexity-analysis-of-binary-search/
- https://leetcode.com/problems/search-in-rotated-sorted-array/
- https://www.youtube.com/watch?v=6ysjqCUv3K4