首先了解什么是数据结构和算法
数据结构 = 数据结构 + 算法
数据结构：用来存储数据的数组
算法：暴力搜索，二分搜索
二分搜索：是一个搜索某个值的索引的算法
条件：在一个有序的数组中查找一个特定的元素 X
算法思路：
1）从数组的中间元素开始，如果中间元素正好是X，而查找成功
2）如果不是中间元素，则利用中间元素，将数组分为前后两个子数组
如果X小于中间位置的元素，则进一步查找前一个子数组
如果X大于中间位置的元素，则查找后一个子数组
3）重复以上步骤，直到找到满足条件的元素，或直到子数组不存在为止，代表查找不成功
实现二分查找的方法有两种
方法一：利用while循环的方法
// 给定一个有序（非降序）数组，可能含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1
// target = 7 ,return 5
// target = 8, return -1
function binary_search (arr , item){
let low = 0
height = - 1
while(low < height){
let mid = parseInt((height + low) / 2)
let guess = arr[mid]
if(guess == item){
return mid
}else if(guess > item){
height = mid - 1
}else{
low = mid + 1
}
}
return -1
}
let myArr = [1,2,3,5,6,7,7,10]
(binary_search(myArr,7)); // 最后输出的是7对应的索引下标 5
(binary_search(myArr,8)); // 找不到8 输出的是 -1方法二：利用递归实现，使用if依次递归，找到相应的值
// 给定一个有序（非降序）数组A，可能含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1
// target = 7 ,return 5
// target = 8, return -1
function binary_search(arr, low, height, key) {
if (low > height) {
return -1;
}
var mid = parseInt((height + low) / 2);
if (arr[mid] == key) {
return mid;
} else if (arr[mid] > key) {
height = mid - 1;
return binary_search(arr, low,height, key);
} else if (arr[mid] < key) {
low = mid + 1;
return binary_search(arr, low, height, key);
}else{
return -1
}
}
let myArr = [1,2,3,5,6,7,7,10]
(binary_search(myArr,1,10,7));
(binary_search(myArr,1,10,8));时间复杂度：总共有n个元素，切换的次数n,n/2,n/4,....n/2^k，其中k就是循环的次数，由于n/2^k取整后>=1，即令n/2^k=1，可得k=log2n,（是以2为底，n的对数）
O(log2n) => O(logn)
优点：比较次数少，查找速度快，平均性能好。
缺点：要求待查表为有序表，且插入删除困难。
结论：适用于不经常变动而查找频繁的有序列表。