Binary Search is an efficient algorithm for finding a specific value in a sorted array. The basic idea of binary search is to repeatedly narrow down the portion of the array that contains the desired value by splitting the array in half. In this article, we will provide a detailed explanation of the binary search algorithm and solve a problem using it.<\/p>\n
The following is a problem that can be solved using binary search:<\/p>\n
Given a sorted array The binary search algorithm proceeds with the following steps:<\/p>\n The time complexity of binary search is Now, let’s write the code to solve the above problem. First, we define a function that accepts the array and target.<\/p>\n In the above code, the Below is an example execution of the binary search function:<\/p>\nnums<\/code> and an integer target<\/code>, return the index of target<\/code>. If target<\/code> does not exist in the array, return -1. The function assumes that nums<\/code> is sorted in ascending order.<\/p>\nExamples<\/h3>\n
\nInput: nums = [-1,0,3,5,9,12], target = 9\nOutput: 4\n\nInput: nums = [-1,0,3,5,9,12], target = 2\nOutput: -1\n<\/pre>\n
Principle of the Binary Search Algorithm<\/h2>\n
\n
\n
O(log n)<\/code>, which allows for quick searches in large datasets.<\/p>\nProblem-Solving Process<\/h2>\n
\nfunction binarySearch(nums, target) {\n let left = 0;\n let right = nums.length - 1;\n\n while (left <= right) {\n const mid = Math.floor((left + right) \/ 2); \/\/ calculate the middle index\n \n if (nums[mid] === target) {\n return mid; \/\/ return middle index if found\n } else if (nums[mid] < target) {\n left = mid + 1; \/\/ move to the right half\n } else {\n right = mid - 1; \/\/ move to the left half\n }\n }\n\n return -1; \/\/ return -1 if the value does not exist\n}\n<\/code><\/pre>\nCode Explanation<\/h3>\n
binarySearch<\/code> function performs binary search on the nums<\/code> array using the target<\/code> value as an argument.<\/p>\n\n
left<\/code> and right<\/code> variables. The initial values are the start and end indices of the array, respectively.<\/li>\nleft<\/code> is less than or equal to right<\/code>.<\/li>\ntarget<\/code>.<\/li>\nExample Execution<\/h2>\n
\nconst nums = [-1,0,3,5,9,12];\nconsole.log(binarySearch(nums, 9)); \/\/ Output: 4\nconsole.log(binarySearch(nums, 2)); \/\/ Output: -1\n<\/code><\/pre>\nResult Analysis<\/h3>\n