Likou Daily Question - Day 46 - 704. Binary Search

2022.7.30 Did you write the questions today?

---

Title:

Given an n-element sorted (ascending) integer array nums and a target value target , write a function to search for target in nums and return the subscript if the target value exists, otherwise return -1.

Analysis:

Given an ascending array and an integer, find out whether the integer exists in the array, return the subscript if it exists, or -1 if it does not exist.

Ideas: For the search problem: The first idea is binary search.Use two subscripts, one left and one right, to start from both ends.Determine whether the middle value is the same as the target, and adjust the subscript according to the size relationship.

When target>num, it means that the target value is on the right of num, then left changes

When target

Analysis:

1. Dichotomy

class Solution {public:int search(vector& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right){int mid = (right - left) / 2 + left;int num = nums[mid];if (target > num){left = mid + 1;}else if (target < num){right = mid - 1;}else{return mid;}}return -1;}};

2. Violence Law

Directly traverse the array. When the traversed element is less than the target, it will continue to traverse. When it is equal, it returns the subscript, and when it is greater than the situation, it returns -1

class Solution {public:int search(vector& nums, int target) {int i=0;while(i