Binary Search

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. Examples Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1 Constraints 1 <= nums.length <= 10^4 -10^4 < nums[i], target < 10^4 All the integers in nums are unique. nums is sorted in ascending order. Explanation Before we jump into the solution, let’s figure out what the requirements for a binary search algorithm are and how it is going to work. The main requirement for binary search is that the input must be sorted. ...

What is binary search? Binary search is an algorithm that helps find an element in a sorted array in O(log n) time. Why should the input be sorted before performing binary search? The input array for binary search needs to be sorted because the algorithm eliminates half of the choices at each step. If the guessed value is greater than the target value, it knows that the right part can’t contain the target value. ...