Binary Search

• Binary Search Version 1:

  public boolean binarySearch(int[] nums, int target) {
    int low = 0;
    int high = nums.length - 1; // 注意点1
    while (low <= high) { //注意点2
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            return true;
        }
        if (nums[mid] > target) {
            high = mid - 1; //注意点3
        } else {
            low = mid + 1;
        }
    }
    return false;
  }
  

• 找到刚好比val大的index

int binarySearch(int[] last, int start, int end, int val) {
    while(start < end) {  //没有等于
        int mid = start + (end-start)/2;
        if (last[mid] > val) {
            end = mid;
        } else if (last[mid] < val) {
            start = mid+1;
        } else {
            return mid; //没有减1
        }
    }

    return end;
}

• find peak element

int low = 0, mid = 0, high = nums.length - 1;
while(low < high) {
    mid = low + (high-low)/2;
    if(nums[mid] < nums[mid+1]) { // 此处的比较
        low = mid+1;
    } else {
        high = mid;
    }
}
return low;