Sorting, dichotomy

One 、 matters needing attention
1 name :
Mandatory rules : Numbers , Underline , Case letters , Dollar symbol , The number can't start , You can't use keywords and reserved words
Non mandatory rules : Look at the text and know the meaning , Hump nomenclature
Variable name and method name , Initial lowercase user, userService
Class names are capitalized User , UserService
2 notes
3 communicate
Two 、 Sort
Sort This means that the saved elements are sorted and stored according to certain rules

such as achievement Sort in descending order , Top three in the class Just take the first three data
2.1 Bubble sort
1 Compare adjacent elements . If the first one is bigger than the second one , Just swap them .
2 Do the same for each pair of adjacent elements , From the beginning of the first couple to the end of the last couple . At this point , The last element should be the largest number .
3 Repeat the above steps for all elements , Except for the last one . 4 Keep repeating the above steps for fewer and fewer elements each time , Until there's no pair of numbers to compare .

2.2 Selection sort
1 Put the smallest one on the left and take out the first one every time , The assumption is the smallest , Then compare with the following one by one , If there is one smaller than the first , Just exchange subscripts after a round of comparison , The subscript of the smallest element has been obtained , Then put it in the front for transposition
2 Repeat this step , Until after the current element When there are no other elements End

3. Look for the element

3.1 In order to find

3.2 Two points search
/**
* Two points search , Also known as half query
*
* 1 The data must be orderly
*
* 2 Generally used for fixed data , Because of order , So adding and deleting is a little more troublesome , Also consider the element shift problem
*
* 3 Both ascending and descending are OK , Just change the algorithm judgment
*
* 4 Random query performance is good
*
* Algorithm implementation
*
* 1 Determine the beginning and end of the intermediate data
* 2 With target data and Compare intermediate data
* 3 If the target data is equal to the intermediate data , Return the index of intermediate data
* 4 If the target data is larger than the intermediate data , Then continue to search in the second half , start = middle +1, End unchanged , Then generate intermediate data
* 5 If the target data is smaller than the intermediate data , Take the first half , Initial invariance , end = middle -1, Then generate intermediate data
* 6 Repeat the above steps , If you start Greater than end Description not found , return -1
*
* @param arr
* @param target
* @return
*/
public static int binarySearch(int[] arr, int target) {
// 1 Determine the beginning and end of the intermediate data
int startIndex = 0;
int endIndex = arr.length-1;
int m = (startIndex+endIndex) /2;

	//  Cycle comparison 
	while (startIndex <= endIndex) {
		// 3  If the target data is equal to the intermediate data , Return the index of intermediate data 
		if (target == arr[m]) {
			return m;
		}
		//  If the target data is larger than the intermediate data , Then continue to search in the second half , start = middle +1, End unchanged , Then generate intermediate data 
		if (target > arr[m]) {
			startIndex=m+1;
		}else{
			//  If the target data is smaller than the intermediate data , Take the first half , Initial invariance , end = middle -1, Then generate intermediate data 
			endIndex = m-1;
		}
		//  Generate intermediate data 
		m = (startIndex+endIndex) /2;
	}
	
	//  Can be implemented here  ,  Indicates that there is no 
	return -1;
}