Today I will be writing about how to solve the Binary Search algorithm problem on Leetcode.
The problem:
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
var search = function(nums, target) {
};
Step 1. Create 2 pointers, left and right to point to the beginning and end of the array.
var search = function(nums, target) {
let left = 0;
let right = nums.length - 1
};
Considering the given example array [-1,0,3,5,9,12], left would point to -1 and right would point to 12.
Step 2. Create while loop.
We will set left = right because they will eventually meet. We also want to find a middle element.
var search = function(nums, target) {
//step 1. create 2 pointers, left and right to point to first and last elements.
let left = 0;
let right = nums.length - 1
while (left <= right){
let middle = left + Math.floor((right - left) / 2)
}
};
Step 3. Write if-statement to calculate middle element.
If the middle element === target, return middle.
var search = function(nums, target) {
let left = 0;
let right = nums.length - 1
while (left <= right){
let middle = left + Math.floor((right - left) / 2)
if(nums[middle] === target){
return middle
} else if (middle < target) {
left = middle + 1
} else {
right = middle - 1
}
}
};
Step 4. Return -1 if element does not match target.
var search = function(nums, target) {
let left = 0;
let right = nums.length - 1
while (left <= right){
let middle = left + Math.floor((right - left) / 2)
if(nums[middle] === target){
return middle
} else if (middle < target) {
left = middle + 1
} else {
right = middle - 1
}
}
return -1
};
Top comments (0)