LeetCode 704 - Binary Search

https://leetcode.com/problems/binary-search/

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

Note:

1. You may assume that all elements in nums are unique.
2. n will be in the range [1, 10000].
3. The value of each element in nums will be in the range [-9999, 9999]

https://leetcode.com/articles/binary-search/

• Initialise left and right pointers : left = 0, right = n - 1.
• While left <= right :
  • Compare middle element of the array nums[pivot] to the target value target.
    • If the middle element is the target target = nums[pivot] : return pivot.
    • If the target is not yet found :
      • If target < nums[pivot], continue the search on the left right = pivot - 1.
      • Else continue the search on the right left = pivot + 1.

public int search(int[] nums, int target) {
  int pivot, left = 0, right = nums.length - 1;
  while (left <= right) {
    pivot = (left + right) / 2;
    if (nums[pivot] == target) return pivot;
    else {
      if (target < nums[pivot]) right = pivot - 1;
      else left = pivot + 1;
    }
  }
  return -1;
}

https://leetcode.com/problems/binary-search/discuss/151320/concise-Java-solution-beats-100

    public int search(int[] nums, int target) {
        // corner case
        if (nums == null || nums.length == 0) return -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }

https://leetcode.com/problems/binary-search/discuss/157435/Java-Solution

public int search(int[] nums, int target) 
{
    int lo = 0;
    int hi = nums.length - 1;

    while(lo <= hi)
    {
     int mid = (lo + hi) >>> 1;

     if(nums[mid] < target)
      lo = mid + 1;
     else if(nums[mid] > target)
      hi = mid - 1;
     else
      return mid;
    }

    return -1;
}

X. https://leetcode.com/problems/binary-search/discuss/150017/recursive-Java-solution

    public int search(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length - 1);
    }
    public int binarySearch(int[] nums, int target, int left, int right) {
        if (left > right) return -1;
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            return binarySearch(nums, target, mid + 1, right);
        } else {
            return binarySearch(nums, target, left, mid - 1);
        }   
    }

https://leetcode.com/problems/binary-search/discuss/167292/Python-recursive-%2B-iterative-easy-to-understand

2. recursive, O(log(N)) time. There is a minor detail that is easy to make mistake. The if condition to control case where left is at least smaller or equal to right, which prevent from endless call to the stack.

    def search(self, nums, target):
        def recur_search(nums,target,left,right):
            if left <= right:
                mid = (left+right)//2
                if nums[mid] == target:
                    return mid
                elif nums[mid] < target:
                    return recur_search(nums,target,mid+1,right)
                else:
                    return recur_search(nums,target,left,mid-1)
            else: return -1
        
        left,right = 0, len(nums)-1
        return recur_search(nums,target,left,right)