Binary search

Binary search

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

Mid + 1 = mid + 1 = mid + 1 = mid + 1 = mid + 1 = mid + 1 = mid + 1

function search(nums, target) { return BinarySearch(nums, start, end, target) } function BinarySearch(arr, s, e, // Let mid = math.floor ((s + e) / 2); // Let mid = math.floor ((s + e) / 2); if(arr[mid] === target) { return mid } else if(arr[mid] > target) { return BinarySearch(arr, s, mid - 1, Else {return BinarySearch(arr, mid + 1, e, target)}} if(arr[s] === target) return s If it is equal, return -1; if not, return -1;}Copy the code

278. The first incorrect version

You are a product manager, currently leading a team to develop a new product. Unfortunately, the latest version of your product did not pass the quality test. Since each version is based on the previous version, all versions after the incorrect version are incorrect.

Suppose you have n versions [1, 2… n] and you want to find the first incorrect version that causes all subsequent versions to fail.

You can tell if version failed in unit tests by calling the bool isBadVersion(version) interface. Implement a function to find the first incorrect version. You should minimize the number of calls to the API.

If isBadVersion is called as little as possible, use binary lookup to get the median value each time. If the median value is the wrong version, narrow the range down to 0 to the median, otherwise to n

var solution = function (isBadVersion) { return function (n) { return BinarySearch(1, n, isBadVersion) }; }; function BinarySearch(s, e, isBadVersion) { while (s < e) { let mid = Math.floor((e + s) / 2) if (isBadVersion(mid)) { return BinarySearch( 0, mid, } else {return BinarySearch(mid + 1, e,); isBadVersion) } } if (e === s) return s }Copy the code

The time is O(logn), assuming we find the change X times, n/2 X ^xx = 1 then X =O(logn) then the space is O(1).

35. Search for insertion locations

Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order.

You can assume that there are no duplicate elements in the array. Binary search, if there is a binary search, return the index directly, if not, when start === end, the position to insert is somewhere near there, either start or start + 1

var searchInsert = function (nums, target) { return BinarySearch(nums, 0, nums.length - 1, target); }; function BinarySearch(arr, s, e, target) { while (e - s > 0) { let mid = Math.floor((s + e) / 2); if (arr[mid] === target) { return mid; } else if (arr[mid] > target) { return BinarySearch(arr, s, mid - 1, target); } else { return BinarySearch(arr, mid + 1, e, target); If (target > arr[s]) {return s + 1; } else { return s; }}Copy the code

Time order logn, same sort in place algorithm as above