I. Binary Search

#704. Binary Search (二分查找法原型代)

Recursive is easier to write and understand;

While loop is more complicated to write, but not easy to enter dead loop, and you'll impresive the interviewer because most interviewees prefer recursive.

If it's too complicated to code with while then use recursive to save time, otherwise use while.

Key point:

• start + 1 < end （防止死循环）

• mid = start + (end-start)/2

• A[mid] =, < , >

• A[start] A[end] ? target

Java

class Solution{
    public int binarySearch(int[] nums, int target){
        int result = -1, start = 0, end = nums.length-1, mid;
        if(num.length == 0){
            return result;
        }    
        while(start+1 < end){
            mid = start + (end - start)/2;
            if(target > nums[mid]){
                start = mid;
            }
            else if(target < nums[mid]){
                end = mid;
            }
            else{
                result = mid;
                break;
            }
        }
        if(target == nums[start]){
            result = start;
        }
        else if(target == nums[end]){
            result = end;
        }
        return result;
    }
}

Python

Python-递归

Python(II)更高效

Python(II)-递归

Binary search time complexity is $O(lgN)$ , space comlexity is $O(lgN)$

There are two common coding:

1. while loop condition: left <= right, compare with target, the stop situation is left == right + 1

// Some code

left = 0
right = len(nums) - 1
while left <= right:
    mid = left + (right - left) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] > target:
        right = mid - 1
    else:
        left = mid + 1

return -1

2. while loop condition: left < right, compare with right element, the stop condition is left == right. The example questions are: #162 PeakElement, #22 Search Rotated Array

// Some code

left = 0
right = len(nums) - 1
while left < right:
    mid = left + (right - left) // 2
    if nums[mid] < nums[right]
        left = mid + 1
    else:
        right = mid
return left // or return right