Binary search

Leetcode-cn.com/problems/bi…

• Given an ordered (ascending) integer array nums with n elements and a target value, write a function to retrieve the target in NUMs, returning a subscript if the target value exists, and -1 otherwise.

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var search = function(nums, target) {
    var len = nums.length;
    var left = 0, right = len - 1;
    if(len === 1) {return target === nums[0]?0 : -1;
    }
    while(left <= right){
        var mid = Math.floor((left + right) / 2); // round down
        if(target < nums[mid]){ // The target value is on the left
            right = mid - 1
        }else if(target > nums[mid]){ // The target value is on the right
            left = mid + 1
        }else{ // The target value is in the middle
            returnmid; }}return -1;
};
Copy the code

– for example, find the target value 10 in [10,11,22,33,44,55,66];

The array of 10 has an index of 0; The index of 66 is 6;

The minimum value	The median	The maximum	instructions
0	3	6	The intermediate value of subscripts 0 and 6 is (0+6)/2=3, the corresponding value of subscript 3 is 33, and the target value is 10<33; Then the new maximum subscript is 3-1=2
0	1	2	Array subscripts 0 and 2 are intermediate values (0+2)/2=1, index 1 is 11, target value 10<11; The new maximum subscript is 1-1=0
0	0	0	Array 0= (0+0)/2=0, index 0= 10, target value 10==10; The result is 10 pairs of deserve subscript 0

Find the minimum value in the rotation sort array

Leetcode-cn.com/problems/fi…

/ * * *@param {number[]} nums
 * @return {number}* /
var findMin = function(nums) {
    var len = nums.length
    if(len === 1) {return  nums[0]}var left = 0, right = len - 1;
    while(left <= right){
        var mid = Math.floor((left + right)/2);
        if(nums[mid] <= nums[right]){ // If the median value is less than the rightmost value, the minimum value is equal to the median value or on the left
            if(nums[mid] > nums[mid-1]){
                right = mid - 1;
            }else{ // The minimum value is equal to the middle value
                return nums[mid]
            }
        }else{ // If the median value is greater than the rightmost value, the minimum value is on the right
            left = mid + 1}}return nums[left]
};
Copy the code

Search rotation sort array

Leetcode-cn.com/problems/se…

• The integer array NUMs is sorted in ascending order. The values in the array are not equal.
• Before passing to the function, NUMs is rotated on some previously unknown subscript k (0<=k<=nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]]. For example, [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2] when rotated at subscript 3.
• Give you the rotated array nums and an integer target, return its subscript if nums contains the target value, otherwise -1.

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number}* /
var search = function(nums, target) {
    var len = nums.length
    if(len === 1) {return nums[0] === target?0: -1;
    }
    var left = 0, right = len -1;
    while(left <= right){
        var mid = Math.floor((left + right) / 2)
        if(target === nums[mid]){
            return mid;
        }
        // Draw a curve and divide it into three sections
        // The middle number is less than the rightmost number
        if(nums[mid] <= nums[right]){  
            if(target > nums[right]){
                right = mid - 1 
            }else if(target < nums[mid]){
                right = mid - 1
            }else{
                left = mid + 1}}else{
            if(target > nums[mid]){
                left = mid + 1
            }else if(target < nums[left]){
               left = mid + 1
            }else{
               right = mid - 1}}}return -1;
    
};



Copy the code

Search rotated sorted array II

Leetcode-cn.com/problems/se…

• The integer array NUMs is sorted in ascending order, and the values in the array need not be different

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {boolean}* /
var search = function(nums, target) {
    var len = nums.length
    if(len == 1 && target == nums[0]) {return true
    }
    var left = 0, right = len - 1
    while(left <= right){
        var mid = Math.floor((left + right) / 2)
        if(target === nums[mid]){
               return true
        }
        if(nums[left] === nums[mid] && nums[mid] === nums[right] ){ // Special handling of equality cases
            left ++
            right --
        }else if(nums[mid] <= nums[right]){ // The right side is in ascending order
          if (target > nums[mid] && target <= nums[right]){
               left = mid + 1
           }else{
               right = mid  - 1}}else { // The left side is in ascending order
            if(target >= nums[left] && target < nums[mid]){
                right = mid - 1
            }else{
                left = mid + 1}}}return false
}
Copy the code

A single element in an ordered array

Leetcode-cn.com/problems/si… Given an ordered array of integers, where every element appears twice and only one number appears only once, find the number.

/ * * *@param {number[]} nums
 * @return {number}* /
var singleNonDuplicate = function(nums) {
    var len = nums.length
    var left = 0, right = len - 1
    while(left <= right){
        var mid = Math.floor((left + right) / 2)
        // Check whether the middle position is odd or even
        // The middle position is even, followed by an even number of integers
        // The middle position is odd, followed by an odd number of integers

        var double = false
        if(mid%2= = =0){
            double = true
        } 
        if(nums[mid] === nums[mid + 1]) {if(double){// There is an even number of integers on the left, even numbers on the right
                left = mid + 2
            }else{// The middle position is odd, and the left side has an odd number of integers, although the odd number is on the left side
                right = mid - 1}}else if (nums[mid] === nums[mid - 1]) {if(double){ // There is an even number of integers on the left, and there is an odd number of integers on the left
                right = mid - 2
            }else{ // There is an odd number of integers on the left, and there is an even number of integers on the right
                left = mid + 1}}else{
            return nums[mid]
        }
    }
};
Copy the code

Looking for peak

Leetcode-cn.com/problems/fi…

• Peak elements are those whose values are greater than their left and right neighbors
• Given an input array nums, find the peak element and return its index. The array may contain multiple peaks, in which case you simply return the location of any one of the peaks.

/ * * *@param {number[]} nums
 * @return {number}* /
var findPeakElement = function(nums) {
    var len = nums.length
    var left = 0, right = len - 1
    while(left < right){
        var mid = Math.floor((left + right)/2)
        if(nums[mid] > nums[mid + 1]) {//
            right = mid
        }else{
            left = mid + 1}}return left
};
Copy the code

Var nums =,2,1,3,5,6,4 [1]

1. Left =0 right=6 mid=3 nums[3]=3 nums[4]=5 nums[3]
2. Left =4 right=6 mid=5 nums[6]= 6 nums[5]>nums[6
3. Left =4 right=5 mid=4 nums[4]=5 nums[5]=6 nums[4]
4. Left =5 right=5 while loop end