leetcode_gym/_problems/binarySearch.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Binary Search	2020-07-23	binary search	https://leetcode.com/tag/binary-search/	Attempted

Problem

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.


Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Solution

{% highlight python %}

def search(self, nums: List[int], target: int) -> int:

def binSearch(low, high, target, nums):
    
    print(low, high, nums, target)
    
    while low<=high:
    
        mid = (low+high)//2

        if nums[mid]==target:
            return mid
        elif target>nums[mid]:  # if target is greater, ignore left half
            low = mid+1
        else:                   # if target is smaller, ignore right half
            high = mid-1
    
    return -1

return binSearch(0, len(nums)-1, target, nums)

{% endhighlight %}